Рекурентни отношения

[Methuselah]

Дайте някой сайт или обяснете как да намерим формула за n-тия член на рекурентно зададена редица...
Например:
редицата зададена по правилото:
а1=1
а2=2*а1+1

се изразява с формулата a_n=2ⁿ-1

[Реклама]

[xyz]

Ако уравненията не са линейни, то нещата се усложняват. Иначе уравнението:
[tex]a_{n+1}-2*a_n-1=0[/tex]
е почти диференчно уравнение, т.е. разликата при тях е, че няма свободен член. За да се отървем от свободния член в случая може да направим полагане: b_n=a_n+e, така че константата "e" ще изберем така, че да подне свободния член:
[tex]b_{n+1}-2*b_n=0,~~\, e=1[/tex].

Сега вече имаме нормално диференчно уравнение, а теорията им е сравнително проста и се състои в следното:
Заменяйки b_{n} с x^n ще получиш уравнение. В случая то е:
[tex]x^{n+1}-2*x^n=0 \Leftrightarrow x^{1}-2*x^{0}=0[/tex],
т.е. в случая умаме уравнение от първа степен. Ясно е, че ако x е корен на последното уравнение, то той е корен и на предходното, откъдето b_n:=xⁿ е решение на рекурентното уравнение (в случая x=2).

За завършване на теорията трябва да отбележим, че очевидно решенията образуват линейно пространство (относно почленното им събиране). Размерността му е колкото степента на полинома (в горния случай 1). Това се доказва лесно, показвайки, че (1,0,...,0) (0,1,...,0)...(0,0,...,1) образуват базис (взимаш произволно решение и опитваш да го нулираш събирайки с горните вектори умножени подходящо). По-горе показахме едно решение. За останалите корени се получават други решения, а останалите корени са n на брой, т.е. ще образуват базис, ако всички те са различни помежду си (е, трябва да се докаже и че са независими).
Случаят при който уравнението има кратни корени е малко по-голяма играчка (търси се производна и т.н.).

Различните корени

[Methuselah]

Благодаря ти много.
Ще пробвам с числата на Фибоначи:
a₁=1
a₂=1
a_n=a_n-1+a_n-2

a_n-a_n-1-a_n-2=0
xⁿ-x^n-1-x^n-2=0
x²-x-1=0
x_1,2=(1±√5)/2

Т.е. решение е:
[tex](\frac{1 \pm sqrt{5} }{2 } )^{n+1}-(\frac{1\pm sqrt{5} }{2 })^n -1= a_{1}[/tex]

Това не е точно така май... има някои неща които липсват от формулата.

[xyz]

[HeypaBHobeceH]

добре, то сайтове да си има(в отговор на r2d2)
но аз искам да попитам за още една задачка, ако някой му се занимава:
а₀ = 0;
а_n = 2a_n/2 +c
където n≥1 , n=2^k;

[Irrefutable]

HeypaBHobeceH,
[tex]a_{n} = \frac{c* ( (1+\sqrt{q+c} )^{n } - (1+\sqrt{q+c} )^{n } }{ 2*\sqrt{1+c} ) } [/tex] , където n := ln(n);
Много е вероятно някъде да съм сбъркал, защото се получи доста сложно.
Идеята е следната ти имаш че[tex] n = 2^{k} [/tex] А в формулата [tex]a_{n} [/tex]зависи от [tex]a_{n/2}[/tex]Можеш да направиш нова рекурентна формула където
[tex]a_{n} = 2*a_{n-1} + c [/tex]и n е всяко естествено число.
След това да си изразиш с х^2 - х- c , да му намериш корените. Да заместиш в а0 и а1 и в [tex]a_{n} = C_{1}*(x_{1})^{n} + C_{2}*(x_{2})^{n}[/tex]Като заместиш an със a1 и a2 , получаваш система за C1 и C2 решаваш системата получаваш формулата за an.

[HeypaBHobeceH]

Irrefutable мерси мн!
направи от 2-но по-сложна на пръв поглед задача, задача на 2 реда че дори я разбрах

би ли ми казал само още нещо - какво правим когато вместо константа накрая : a_n-a_n-1 - C =0,
имаме : a_n-a_n-1 - n=0?

[Irrefutable]