Монгол Бодлогын Сан

Заавар: $\displaystyle S_n=\sum\limits_{0\le k\le\frac n2}\binom{n-2k}{k}\alpha^k$ гэвэл $S_n=S_{n-1}+\alpha S_{n-3}+[n=0]$ гэж харуул.

Бодолт: $\displaystyle S_n=\sum\limits_{0\le k\le\frac n2}\binom{n-2k}{k}\alpha^k$ гэе. Тэгвэл \begin{align*} S_n&=\sum\limits_{0\le k\le\frac k2}\binom{n-2k}{k}\alpha^k=\sum\limits_{k}\binom{n-2k}{k}\alpha^k\\ &=\sum\limits_{k}\binom{n-2k-1}{k-1}\alpha^k+\sum\limits_{k}\binom{n-2k-1}{k}\alpha^k & & \color{red}{\leftarrow\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}}\\ &=\alpha\sum\limits_{k}\binom{n-3-2(k-1)}{k-1}\alpha^{k-1}+\sum\limits_{k}\binom{n-1-2k}{k}\alpha^k\\ &=\alpha S_{n-3}+S_{n-1} \end{align*} $S_{n}=0$, $n<0$ гэвэл $S_{0}=1$, $S_{1}=1$, $S_2=1+\alpha$ тул $S_n=S_{n-1}+\alpha S_{n-3}+[n=0]$ болно. Иймд $$S(z)=\dfrac{1}{1-z-\alpha z^3}$$ болох ба $\alpha=-\dfrac4{27}$ үед \begin{align*} S(z)&=\dfrac{1}{1-z+\frac{4}{27}z^3}=\dfrac{1}{\big(1+\frac{1}{3}z\big)\big(1-\frac{2}{3}z)^2}\\ &=\dfrac{A}{1+\frac{1}{3}z}+\dfrac{B}{1-\frac23 z}+\dfrac{C}{(1-\frac23 z)^2}\\ \end{align*} болох тул $$1=A\left(1-\frac23z\right)^2+B\left(1+\frac13z\right)\left(1-\frac23z\right)+C\left(1+\frac13z\right)$$ байна. $z=-3$ үед $1=A\cdot\left(1-\dfrac23\cdot(-3)\right)^2$ тул $A=\dfrac{1}{9}$, $z=\dfrac32$ үед $1=C\cdot \dfrac{3}{2}$ тул $C=\dfrac{2}{3}$ байна. Түүнчлэн $z=0$ гэвэл $$1=\dfrac19+B+\dfrac23\Rightarrow B=\dfrac{2}{9}$$ болно. Иймд $$S_n=\dfrac{1}{9}\left(-\dfrac13\right)^n+\dfrac{2}{9}\left(\frac23\right)^n+\dfrac{2}{3}(n+1)\left(\frac23\right)^n$$ буюу $$S_n=\left(\frac23n+\dfrac89\right)\left(\frac23\right)^n+\frac19\left(-\frac13\right)^n$$ болов.