Homework

Problem 1 用生成函数求解递推式 $$ a_{n} = 4a_{n-1} - 5a_{n-2} + 2a_{n-3} $$ 初始值为 $ a_{0}=0,a_{1}=3,a_{2}=7 $。 解： 设数列 $ \{ a_{n} \} $ 的生成函数为 $ F(x) $，那么根据递推式和初值 $ a_{0}=0,a_{1}=3,a_{2}=7 $ 得到 $$ F(x) = 4xF(x) - 5x^{2}F(x) + 2x^{3}F(x) + 3x - 5x^{2} $$ 得到 $$ F(x) = \dfrac{5x^{2}-3x}{2x^{3}-5x^{2}+4x-1} = \dfrac{3x-5x^{2}}{(1-x)^{2}(1-2x)} $$ 我们希望分解成 $$ \dfrac{A}{1-x} + \dfrac{B}{(1-x)^{2}} + \dfrac{C}{1-2x} $$ 待定系数可以解得 $$ F(x) = \dfrac{-3}{1-x} + \dfrac{2}{(1-x)^{2}} + \dfrac{1}{1-2x} $$ 展开得到 $$ F(x) = \sum_{n=0}^{\infty} (-3+2(n+1)+2^{n})x^{n} $$ 因此 $$ a_{n} = -3+2(n+1)+2^{n} = 2^{n} + 2n - 1 $$ ...

Exercise 1 Let $ f:\mathbb{R}\to\mathbb{R} $ be a function. Prove that the following are equivalent: (i) There is a constant $ a\in\mathbb{R} $ such that for every$ x\in\mathbb{R} $ we have$ f(x)=ax $. (ii) For all $ x_1,x_2,c,x\in\mathbb{R} $ we have $ f(x_1+x_2)=f(x_1)+f(x_2) $ and $ f(cx)=c\,f(x) $. (i ⇒ ii) Assume there exists $ a\in\mathbb{R} $ such that $ f(x)=a x $ for all $ x\in\mathbb{R} $ . Then for any $ x_1,x_2,c,x\in\mathbb{R} $ , ...

Problem 1 (1) 求 $$ \sum_{k=0}^{n} \binom{ 2n }{ 2k } $$ 解 $$ \begin{align*} & \sum_{k=0}^{n} (-1)^{k}\binom{ n }{ k } = 0 \\ \implies & \sum_{k=0}^{2n} (-1)^{k}\binom{ 2n }{ k } =0 \\ \implies & \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } \end{align*} $$ 同时由于 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } + \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } = \sum_{k=0}^{2n} \binom{ 2n }{ k } = 2^{2n} $$ 得到 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = 2^{2n-1} $$ ...