# What is the limit of...

$$\prod\limits_{n\ge2}\left(1+\frac{1}{n^2}\right)$$

# Using generating functions to solve recurrence relations

1. ak = ak-1 + 2ak-2 + 2k, a0 = 4, a1 = 12
2. ak = 4ak-1 - 4ak-2 + k2, a0 = 2, a1 = 5
3. ak = 2ak-1 - 3ak-2 + 4k + 6, a0 = 20, a1 = 60

• Problem 1

$\phantom{\rule{.85em}{0ex}}\left\{\begin{array}{l}{a}_{k}={a}_{k-1}+2{a}_{k-2}+{2}^{k}\\ {a}_{0}=4\\ {a}_{1}=12\end{array}\right\$我们首先令f(x)为序列{ak}的生成函数，即$\phantom{\rule{.85em}{0ex}}\mathit{\text{f}}\left(x\right)=\sum _{k\ge 0}{a}_{k}\phantom{\rule{.2em}{0ex}}{x}^{k}$然后我们对递推关系式（也就是上面大括号中的第一个式子）中的每一项都乘以xk，得$\phantom{\rule{.85em}{0ex}}{a}_{k}{x}^{k}={a}_{k-1}{x}^{k}+2{a}_{k-2}{x}^{k}+{2}^{k}{x}^{k}$接着对每一项都取k从2开始的和$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{a}_{k}{x}^{k}=\sum _{k\ge 2}{a}_{k-1}{x}^{k}+\sum _{k\ge 2}2{a}_{k-2}{x}^{k}+\sum _{k\ge 2}{2}^{k}{x}^{k}$$\phantom{\rule{4.85em}{0ex}}\text{=}\sum _{k\ge 2}{a}_{k-1}{x}^{k}+2\sum _{k\ge 2}{a}_{k-2}{x}^{k}+\sum _{k\ge 2}{2}^{k}{x}^{k}$在这之后我们将对每一项都进行变形，变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{a}_{k}{x}^{k}=\left(\sum _{k\ge 2}{a}_{k}{x}^{k}+{a}_{1}x+{a}_{0}\right)-{a}_{1}x-{a}_{0}$$\phantom{\rule{4.85em}{0ex}}\text{=}\sum _{k\ge 0}{a}_{k}{x}^{k}-{a}_{1}x-{a}_{0}$$\phantom{\rule{4.85em}{0ex}}\text{=}\mathit{\text{f}}\left(x\right)-4x-12$$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{a}_{k-1}{x}^{k}=x\sum _{k\ge 2}{a}_{k-1}{x}^{k-1}$$\phantom{\rule{5.95em}{0ex}}\text{=}x\sum _{k\ge 1}{a}_{k}{x}^{k}$$\phantom{\rule{5.95em}{0ex}}\text{=}x\left(\sum _{k\ge 0}{a}_{k}{x}^{k}-{a}_{0}\right)$$\phantom{\rule{5.95em}{0ex}}\text{=}x\left(\mathit{\text{f}}\left(x\right)-4\right)$$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{a}_{k-2}{x}^{k}={x}^{2}\sum _{k\ge 2}{a}_{k-2}{x}^{k-2}$$\phantom{\rule{5.95em}{0ex}}\text{=}{x}^{2}\sum _{k\ge 0}{a}_{k}{x}^{k}$$\phantom{\rule{5.95em}{0ex}}\text{=}{x}^{2}\mathit{\text{f}}\left(x\right)$$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{2}^{k}{x}^{k}=\sum _{k\ge 0}{2}^{k}{x}^{k}-2x$$\phantom{\rule{4.75em}{0ex}}\text{=}\frac{1}{1-2x-1}-2x-1$现在我们将变形后的式子替换回去$\phantom{\rule{.85em}{0ex}}\mathit{\text{f}}\left(x\right)-4x-12=x\left(\mathit{\text{f}}\left(x\right)-4\right)+2{x}^{2}\mathit{\text{f}}\left(x\right)+\frac{1}{1-2x}-2x-1$合并同类项，然后分解分式多项式得$\phantom{\rule{.85em}{0ex}}\mathit{\text{f}}\left(x\right)=\frac{2}{3}\text{·}\frac{1}{{\left(1-2x\right)}^{2}}+\frac{38}{9}\text{·}\frac{1}{1-2x}-\frac{8}{9}\text{·}\frac{1}{1+x}$根据生成函数与序列{ak}的关系，可得$\phantom{\rule{.85em}{0ex}}{a}_{k}\text{=}\frac{2}{3}\mathit{\text{C}}\left(2+k-1,2-1\right){2}^{k}+\frac{38}{9}\text{·}{2}^{k}-\frac{8}{9}\text{·}{\left(-1\right)}^{k}$$\phantom{\rule{1.85em}{0ex}}\text{=}\frac{2}{3}\left(1+k\right){2}^{k}+\frac{38}{9}\text{·}{2}^{k}-\frac{8}{9}\text{·}{\left(-1\right)}^{k}$$\phantom{\rule{1.85em}{0ex}}\text{=}\frac{44}{9}\text{·}{2}^{k}+\frac{2}{3}k\text{·}\frac{k}{3}-\frac{8}{9}\text{·}{\left(-1\right)}^{k}$至此，我们解出了满足递推关系和初始条件的解

• Problem 2

$\phantom{\rule{.85em}{0ex}}\left\{\begin{array}{l}{a}_{k}=4{a}_{k-1}-4{a}_{k-2}+{k}^{2}\\ {a}_{0}=2\\ {a}_{1}=5\end{array}\right\$我们首先令f(x)为序列{ak}的生成函数，即$\phantom{\rule{.85em}{0ex}}\mathit{\text{f}}\left(x\right)=\sum _{k\ge 0}{a}_{k}\phantom{\rule{.2em}{0ex}}{x}^{k}$然后我们对递推关系式（也就是上面大括号中的第一个式子）中的每一项都乘以xk，得$\phantom{\rule{.85em}{0ex}}{a}_{k}{x}^{k}=4{a}_{k-1}{x}^{k}-4{a}_{k-2}{x}^{k}+{k}^{2}{x}^{k}$接着对每一项都取k从2开始的和$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{a}_{k}{x}^{k}=\sum _{k\ge 2}4{a}_{k-1}{x}^{k}-\sum _{k\ge 2}4{a}_{k-2}{x}^{k}+\sum _{k\ge 2}{k}^{2}{x}^{k}$$\phantom{\rule{4.85em}{0ex}}\text{=}4\sum _{k\ge 2}{a}_{k-1}{x}^{k}-4\sum _{k\ge 2}{a}_{k-2}{x}^{k}+\sum _{k\ge 2}{k}^{2}{x}^{k}$在这之后我们将对每一项都进行变形，变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{a}_{k}{x}^{k}=\left(\sum _{k\ge 2}{a}_{k}{x}^{k}+{a}_{1}x+{a}_{0}\right)-{a}_{1}x-{a}_{0}$$\phantom{\rule{4.85em}{0ex}}\text{=}\sum _{k\ge 0}{a}_{k}{x}^{k}-{a}_{1}x-{a}_{0}$$\phantom{\rule{4.85em}{0ex}}\text{=}\mathit{\text{f}}\left(x\right)-5x-2$$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{a}_{k-1}{x}^{k}=x\sum _{k\ge 2}{a}_{k-1}{x}^{k-1}$$\phantom{\rule{5.95em}{0ex}}\text{=}x\sum _{k\ge 1}{a}_{k}{x}^{k}$$\phantom{\rule{5.95em}{0ex}}\text{=}x\left(\sum _{k\ge 0}{a}_{k}{x}^{k}-{a}_{0}\right)$$\phantom{\rule{5.95em}{0ex}}\text{=}x\left(\mathit{\text{f}}\left(x\right)-2\right)$$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{a}_{k-2}{x}^{k}={x}^{2}\sum _{k\ge 2}{a}_{k-2}{x}^{k-2}$$\phantom{\rule{5.95em}{0ex}}\text{=}{x}^{2}\sum _{k\ge 0}{a}_{k}{x}^{k}$$\phantom{\rule{5.95em}{0ex}}\text{=}{x}^{2}\mathit{\text{f}}\left(x\right)$最后的这个k2的和式处理稍微复杂一些$\phantom{\rule{.85em}{0ex}}\sum _{k\ge 2}{k}^{2}{x}^{k}=\sum _{k\ge 0}{k}^{2}{x}^{k}-x$$\phantom{\rule{4.75em}{0ex}}\text{=}x\sum _{k\ge 0}{k}^{2}{x}^{k-1}-x$$\phantom{\rule{4.75em}{0ex}}\text{=}x\sum _{k\ge 0}k\phantom{\rule{.2em}{0ex}}k{x}^{k-1}-x$化简到这一步之后，下面我们对和式积分，然后再求导$\phantom{\rule{4.75em}{0ex}}\text{=x∑k≥0kxk'-x}$$\phantom{\rule{4.75em}{0ex}}\text{=}x{\left(x\sum _{k\ge 0}k{x}^{k-1}\right)}^{\text{'}}-x$再来一次$\phantom{\rule{4.75em}{0ex}}\text{=}x{\left(x{\left(\sum _{k\ge 0}{x}^{k}\right)}^{\text{'}}\right)}^{\text{'}}-x$到了这一步之后就简单了$\phantom{\rule{4.75em}{0ex}}\text{=}x{\left(x{\left(\frac{1}{1-x}\right)}^{\text{'}}\right)}^{\text{'}}-x$$\phantom{\rule{4.75em}{0ex}}\text{=}x{\left(\frac{x}{{\left(1-x\right)}^{2}}\right)}^{\text{'}}-x$$\phantom{\rule{4.75em}{0ex}}\text{=}\frac{x\left(1+x\right)}{{\left(1-x\right)}^{3}}-x$现在我们将变形后的式子替换回去$\phantom{\rule{.85em}{0ex}}\mathit{\text{f}}\left(x\right)-5x-2=4x\left(\mathit{\text{f}}\left(x\right)-2\right)-4{x}^{2}\mathit{\text{f}}\left(x\right)+\frac{x\left(1+x\right)}{{\left(1-x\right)}^{3}}-x$合并同类项，然后分解分式多项式得$\phantom{\rule{.85em}{0ex}}\mathit{\text{f}}\left(x\right)=\frac{2}{{\left(1-x\right)}^{3}}+\frac{5}{{\left(1-x\right)}^{2}}+\frac{13}{1-x}+\frac{6}{{\left(1-2x\right)}^{2}}-\frac{24}{1-2x}$根据生成函数与序列{ak}的关系，可得$\phantom{\rule{.85em}{0ex}}{a}_{k}\text{=}2\mathit{\text{C}}\left(3+k-1,3-1\right)+5\mathit{\text{C}}\left(2+k-1,2-1\right)+13+6\mathit{\text{C}}\left(2+k-1,2-1\right){2}^{k}-24\text{·}{2}^{k}$$\phantom{\rule{1.85em}{0ex}}\text{=}2\frac{\left(2+k\right)\left(1+k\right)}{2}+5\left(1+k\right)+13+6\left(1+k\right){2}^{k}-24\text{·}{2}^{k}$展开、合并同类项$\phantom{\rule{1.85em}{0ex}}\text{=}\left(2+13+5\right)+\left(6\text{·}{2}^{k}-24\text{·}{2}^{k}\right)+\left(3k+5k\right)+6k\text{·}{2}^{k}+{k}^{2}$$\phantom{\rule{1.85em}{0ex}}\text{=}20-18\text{·}{2}^{k}+8k+6k\text{·}{2}^{k}+{k}^{2}$至此，我们解出了满足递推关系和初始条件的解

• Problem 3

Problem 3的和处理方式前面的Problem 1十分相似，这里不再给出解答。
• 总结

• References

# 证明二项分布的逼近

$\phantom{\rule{.85em}{0ex}}\text{P}\left(X=k\right)\text{≈}\frac{{\lambda }^{k}}{k!}{e}^{-\lambda }\left(k\text{= 0, 1, 2, ...}\right)$

# Hot pot & prodigals

• Facing the possibilities

• Prodigals