Общ член на редица

[Pinetop Smith]

Дадена е редица, изпълняваща условията

[tex]a_1 = 1[/tex]
[tex]a_2 = 2[/tex]
[tex]a_n = a_{n-1} + 2a_{n-2} + ... + ka_{n-k} + ... + (n-2)a_2 + (n-1)a_1 + 1[/tex]

Да се намери общия член на редицата(т.е. [tex]a_n[/tex], изразен само чрез n).

[Реклама]

[nikko1]

Още като видях задачата и ми замириса на Фибоначи (Fringe TV Series )

Нека [tex]F_i[/tex] да бъде [tex]i[/tex]-тото число в редицата на Фибоначи.
Ще докажа тъждеството [tex]a_n=F_{2n-1}.[/tex] Ще използвам метод на математическата индукция по индекса n.
1) За
n=1 имаме [tex]a_1=1=F_1[/tex]
n=2 имаме [tex]a_2=a_1+1=2=F_3[/tex]
n=3 имаме [tex]a_3=a_2+2a_1+1=2+2+1=5=F_5.[/tex]
2) Нека твърдението е доказано за всички числа [tex]k\leq n-1, [/tex] т.е.
[tex]a_{n-1}=F_{2(n-1)-1}=F_{2n-3}.[/tex]
Според рекурентната зависимост
[tex]a_n=a_{n-1}+2a_{n-2}+\dots+ka_{n-k}+\dots+(n-2)a_2+(n-1)a_1+1\ \ [/tex] и

[tex]a_{n-1}=a_{n-2}+2a_{n-3}+\dots+(k-1)a_{n-k}+\dots+(n-3)a_2+(n-2)a_1+1.[/tex]

Изваждаме двете равенства

[tex]a_n-a_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+\dots+a_{n-k}+\dots+a_2+a_1[/tex] или

[tex]a_n=a_{n-1}+\sum_{i=1}^{n-1} a_{i}[/tex] но за всички числа в дясната страна на това равенство е в сила твърдението, което доказваме, т.е. членовете на редицата са нечетните членове на редицата на Фибоначи или
[tex]a_n=a_{n-1}+F_{2n-3}+F_{2n-5}+\dots+F_1[/tex]
Използваме третото тъждество
за сумата от нечетните числа на Фобоначи
[tex]\sum_{i=0}^{n-1} F_{2i+1} = F_1+F_3+\dots+F_{2n-1}=F_{2n}[/tex] или [tex]F_{2n-3}+F_{2n-1}+\dots+F_1=F_{2n-2}[/tex]
Заместваме
[tex]a_n=a_{n-1}+F_{2n-2}[/tex], но по индукционно допускане [tex]a_{n-1}=F_{2n-3}.[/tex] и получаваме [tex]a_n=F_{2n-2}+F_{2n-3}=F_{2n-1}[/tex] по основното тъждесто за числата на Фибоначи.

Тъждеството е доказано за всяко естествено число n.

Така [tex]a_n=F_{2n-1}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{2n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{2n-1}}{\sqrt{5}}\,\cdot[/tex]