Монгол Бодлогын Сан
Эх хэлээрээ суралцаж, эх хэлээрээ мэдлэгээ түгээе.
Бодлого №16354
$\sum\limits_{k=0}^n(-1)^k C_{2n-k}^k\cdot2^{2n-2k}=2n+1$ гэж батал.
Бодлогын төрөл: Уламжлалт
Бодлогыг оруулсан: Балхүүгийн Батбаясгалан
Бодолт
Заавар: $a_m=\sum\limits_{k\ge 0}(-1)^k C_{m-k}^k\cdot2^{m-2k}$ дарааллын рекурент харьцаа, уламжлагч функцийг ол.
Бодолт: \begin{align*}
a_m&=\sum\limits_{k\ge 0}(-1)^k C_{m-k}^k\cdot2^{m-2k}=2^{m}+\sum_{k\ge 1}(-1)^k C_{m-k}^k\cdot2^{m-2k}\\
&=2^{m}+\sum_{k\ge 1}(-1)^k C_{m-k-1}^{k}\cdot 2^{m-2k}+\sum_{k\ge 1}(-1)^k C_{m-k-1}^{k-1}\cdot 2^{m-2k}\\
&=2\Big(2^{m-1}+\sum_{k\ge 1}(-1)^k C_{(m-1)-k}^{k}\cdot 2^{(m-1)-2k}\Big)-\sum_{k\ge 1}(-1)^{k-1} C_{(m-2)-(k-1)}^{k-1}\cdot 2^{m-2-2(k-1)}\\
&=2a_{m-1}-a_{m-2}
\end{align*}
Эндээс характеристик тэгшитгэл нь $x^2-2x+1=0$ ба $x=1$ гэсэн давхар шийдтэй тул ерөнхий шийд нь $a_m=c_1m+c_2$ хэлбэртэй байна. $a_0=1$, $a_1=2$ тул
$$\left\{\begin{array}{c}
1=c_1\cdot 0+c_2\\
2=c_2\cdot 1+c_2
\end{array}\right.\Rightarrow c_1=c_2=1$$
буюу $a_m=m+1$ болно. Тухайн тохиолдолд $m=2n$ үед $a_{2n}=2n+1$ болж батлагдав.