Przybliżanie liczby niewymiernej

[suchy1111]

Rozważmy następujące równanie rekurencyjne.
\(\displaystyle{ F (n) = \begin{cases} 2\quad dla \quad n =1\\ \frac{2 \cdot F(n -1) +5}{F(n -1) +2} \quad dla \quad n \ge 1\end{cases}}\)
Uzasadnij, że \(\displaystyle{ \lim_{ x \to \infty } ⁡F(n)= \sqrt{5}}\).
Zadanie próbowałem zrobić na dwa sposoby. Oto pierwszy z nich:
Na początku chciałem określić monotoniczność tego ciągu za pomocą funkcji tworzącej.
\(\displaystyle{ F (n)= \sum_{n=0 }^{\infty} g_{n} x^{n} =
2 + \frac{2 \cdot \sum_{n=1 }^{\infty} a_{n-1} x^{n} + 5 \cdot \sum_{n=1 }^{\infty} x^{n}}{ \sum_{n=1 }^{\infty} a_{n-1} x^{n} + 2 \cdot \sum_{n=1 }^{\infty} x^{n}}}\)
\(\displaystyle{ = 2 + \frac{2x \cdot \sum_{n=1 }^{\infty} a_{n-1} x^{n-1} + 5 \cdot \sum_{n=1 }^{\infty} x^{n}}{ x\sum_{n=1 }^{\infty} a_{n-1} x^{n-1} + 2 \cdot \sum_{n=1 }^{\infty} x^{n}}}\)
\(\displaystyle{ F (n)= 2+ \frac{2xF(n) + \frac{5x^{2} }{1-x} }{xF(n) + \frac{2x^{2} }{1-x}}}\)
\(\displaystyle{ F (n) \cdot xF(n) + \frac{2x^{2} }{1-x} = 2 \cdot xF(n) + \frac{2x^{2} }{1-x} + 2xF(n) + \frac{5x^{2} }{1-x}}\)
\(\displaystyle{ xF(n)^{2} + \frac{2x^{2}F(n) }{1-x} = 2xF(n) + \frac{4x^{2} }{1-x} + 2xF(n) + \frac{5x^{2} }{1-x}}\)
\(\displaystyle{ xF(n)^{2} \cdot (1-x) + 2x^{2}F(n) = 2xF(n)\cdot (1-x)+4x^{2} + 2xF(n)\cdot (1-x) + 5x^{2}}\)
\(\displaystyle{ xF(n)^{2} - x^{2}F(n)^{2} + 2x^{2}F(n) = 2xF(n)-2x^{2}F(n)+4x^{2} + 2xF(n)-2x^{2}F(n) + 5x^{2}}\)
\(\displaystyle{ - x^{2}F(n)^{2} +xF(n)^{2} + 6x^{2}F(n) -4xF(n)- 9x^{2} =0}\)
\(\displaystyle{ (x- x^{2}) \cdot F(n)^{2} + ( 6x^{2}-4x)F(n)- 9x^{2} =0}\)
Teraz szukam wartości które może przyjąć F(n):
\(\displaystyle{ a=(x-x^{2} ),b=(6x^{2} +4x),c= 9x^{2}}\)
\(\displaystyle{ \Delta=(6x^{2} +4x)^{2}- 4 \cdot (x-x^{2}) \cdot 9x^{2} =72 x^{4} + 12 x^{3} + 16 x^{2}}\)
\(\displaystyle{ \sqrt{\Delta} =\sqrt{72 x^{4} + 12 x^{3} + 16 x^{2}} = 2 x \sqrt{(3 x (6 x + 1) + 4)}}\)
\(\displaystyle{ F(n)_{1}= \frac{-6x^{2} -4x - 2 x \sqrt{(3 x (6 x + 1) + 4)}}{2x-2x^{2}}}\)
\(\displaystyle{ F(n)_{2}=\frac{-6x^{2} -4x + 2 x \sqrt{(3 x (6 x + 1) + 4)}}{2x-2x^{2}}}\)
I w tym momencie nie wiem co mam dalej zrobić i czy wg liczenie wartości F(n) miało sens.

Drugi sposobem żeby uzasadnić, że \(\displaystyle{ \lim_{ x \to \infty } ⁡F(n)= \sqrt{5}}\). Było zbadanie czy ciąg \(\displaystyle{ F(n) = \frac{2 \cdot F(n -1) +5}{F(n -1) +2}}\) jest monotoniczny. Lecz niestety badając jego zbieżność, wychodziło mi, że nie jest zbieżny. Dlatego wpadłem na pomysł, że mógłbym podzielić ten ciąg na dwa podciągi, jeden z elementami parzystymi drugi natomiast z nieparzystymi i zbadać dla nich zbieżność.
Ciąg dla elementów parzystch będzie miał wzór \(\displaystyle{ F(2(n+1)) = \frac{2 \cdot F(2n) +5}{F(2n) +2}}\)
Natomiast ciąg dla elementów nieparzystch będzie miał wzór \(\displaystyle{ F(2(n+1)+1) = \frac{2 \cdot F(2n+1) +5}{F(2n+1) +2}}\)
Liczę czy ciąg jest zbieżny i jak tak to w którą stronę:
\(\displaystyle{ F(2(n+2))- F(2(n+1)) =\frac{2 \cdot F(2n+1) +5}{F(2n+1) +2} - \frac{2 \cdot F(2n) +5}{F(2n) +2} = \frac{2F(2n+1)F(2n) +4F(2n+1) +5F(2n) +10}{F(2n+1)F(2n) +2F(2n+1) +2F(2n) +4} = \frac{ F(2n) - F(2n+1)}{F(2n+1)F(2n) +2F(2n+1) +2F(2n) +4} = \frac{ F(2n) - \frac{2 F(2n) +5}{F(2n) +2}}{\frac{ 2F(2n) +5}{F(2n) +2}F(2n) +\frac{4 F(2n) +5}{F(2n) +2} +2F(2n) +4}}\)
\(\displaystyle{ =\frac{ -F(2n) - \frac{1}{F(2n) +2}}{\frac{ 2F(2n) +5}{F(2n) +2}F(2n) +\frac{4 F(2n) +5}{F(2n) +2} +2F(2n) +4}}\)
Czy wystarczy, że znajdę ograniczenie tego ciągu przez liczby dodatnie co by implikowało fakt, że w mianowniku nie będzie liczby ujemnej natomiast licznik będzie ujemny, co z kolei daje nam to, że różnica jest ujemna czyli ciąg jest malejący?
Obliczając ograniczenia skorzystałem z sufitu i podłogi liczby \(\displaystyle{ \sqrt{5}}\)
Udowodnienie, że \(\displaystyle{ F(2(n+1)) = \frac{2 \cdot F(2n) +5}{F(2n) +2}}\) jest ograniczony z góry:
\(\displaystyle{ F(2(n+1)) < \frac{2 \cdot 3 +5}{2 +2} ; F(2(n+1)) < \frac{11}{4} ; F(2(n+1)) < 3,75}\)
Dolne ograniczenie: \(\displaystyle{ F(2(n+1)) > \frac{2 \cdot 2 +5}{3 +2} ; F(2(n+1)) > \frac{9}{5} ; F(2(n+1)) > 2,2}\)
Z ciągiem elementów nieparzystych postąpiłem identycznie:
\(\displaystyle{ F(2(n+2)+1)- F(2(n+1)+1) = ... =\frac{ -F(2n+1) - \frac{1}{F(2n+1) +2}}{\frac{ 2F(2n+1) +5}{F(2n+1) +2}F(2n+1) +\frac{4 F(2n+1) +5}{F(2n+1) +2} +2F(2n+1) +4}}\)
Górne ograniczenie: \(\displaystyle{ F(2n+1) < \frac{2 \cdot 3 +5}{2 +2} ; F(2n+1) < \frac{11}{4} ; F(2n+1) < 3,75}\)
Dolne ograniczenie: \(\displaystyle{ F(2n+1) > \frac{2 \cdot 2 +5}{3 +2} ; F(2n+1) > \frac{9}{5} ; F(2n+1) > 2,2}\)
Jeżeli wszystko do tej pory robię dobrze to mam dwa ciągi jednostajnie zbieżne. Moge zastosować twierdzenie o sumie dwóch ciągów zbieżnych które będzie rozwiązaniem mojego zadania. Niestety nie mam pojęcia jak sie do tego zabrać i jak to obliczyć. W internecie szukałem podobnych zadań ale nigdzie nie umiałem znaleźć zastosowania tego twierdzenia w ciągu z rekurencją.
Proszę o pomoc

[Janusz Tracz]

Napracowałeś się. Co do rozwiązania pierwszą metodą to mam kilka uwag bo nie do końca rozumiem już od pierwszej linijki właściwie. Funkcja tworzącą definiuje się inaczej zapis \(\displaystyle{ F (n)= \sum_{n=0 }^{\infty} g_{n} x^{n}}\) nie wiadomo co znaczy. Co do drugiego rozwiązania to idea jest o wiele lepsza faktycznie można pokazać, że ciąg ten składa się z dwóch monotonicznych podciągów które wyczerpują możliwości poza tym są one ograniczone zatem mają granicę. I od tego momentu pojawił się problem jak mniemam. Więc podpowiem. Skoro podciągi te mają granicę wszak pokazałeś, że tak jest to istnieje taka liczba \(\displaystyle{ g}\), że \(\displaystyle{ \lim_{ n \to \infty } ⁡F(2n)= g}\) oraz \(\displaystyle{ \lim_{ n \to \infty } ⁡F(2n-2)= g}\) to korzystając z rekurencji do \(\displaystyle{ F(2n)}\) można zapisać również, że z ednaj strony granicą jest wspomniane \(\displaystyle{ g}\) a z drugiej:

\(\displaystyle{ \lim_{ n \to \infty } ⁡F(2n)=\lim_{ n \to \infty }\frac{2 \cdot F(2n -1) +5}{F(2n -1) +2}=\lim_{ n \to \infty }\frac{2 \cdot \frac{2 \cdot F(2n -2) +5}{F(2n -2) +2} +5}{\frac{2 \cdot F(2n -2) +5}{F(2n -2) +2}+2}= \frac{ 2 \cdot \frac{2g+5}{g+2}+5 }{ \frac{2g+5}{g+2}+2 }}\)

zatem musi zachodzić \(\displaystyle{ g=\frac{ 2 \cdot \frac{2g+5}{g+2}+5 }{ \frac{2g+5}{g+2}+2 }}\) co trzeba rozwiązać traktując \(\displaystyle{ g}\) jak niewiadomą. Jeśli wyjdą jakieś inne rozwiązania to najprawdopodobniej odpadną bo nie będą spełniać ograniczeń. Analogicznie można postąpić z drugim podciągiem. Powinno wyjść, że dla jednego i drugiego \(\displaystyle{ g= \sqrt{5}}\) wtedy zakończysz dowód.

Alternatywnie można zauważyć, że

\(\displaystyle{ F_n= \frac{2F_{n-1}+5}{F_{n-1}+2}= \frac{2F_{n-1}+4+1}{F_{n-1}+2}=2+ \frac{1}{2+F_{n-1}}}\)

Zatem kolekcje wyrazy ciągu tworzą

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/U%C5%82amek_%C5%82a%C5%84cuchowy

postaci:

\(\displaystyle{ F_{1}=2+ \frac{1}{2+2}=2+ \frac{1}{4}}\)

\(\displaystyle{ F_{2}=2+ \frac{1}{2+2+ \frac{1}{4}}=2+\frac{1}{4+ \frac{1}{4}}}\)

\(\displaystyle{ F_{3}=2+ \frac{1}{2+2+\frac{1}{4+ \frac{1}{4}}}= 2+ \frac{1}{4+\frac{1}{4+ \frac{1}{4}}}}\)

\(\displaystyle{ F_4=2+ \frac{1}{2+2+ \frac{1}{4+\frac{1}{4+ \frac{1}{4}}}}=2+\frac{1}{4+ \frac{1}{4+\frac{1}{4+ \frac{1}{4}}}}}\)

itd.

gdy \(\displaystyle{ n \rightarrow \infty}\) to tych ułamków z \(\displaystyle{ 4}\) będzie nieskończenie wiele, można wtedy zastosować sztuczkę i oznaczyć

\(\displaystyle{ \xi=\frac{1}{4+ \frac{1}{4+\frac{1}{4+ \frac{1}{4+...}}}}}\)

i zauważyć, że \(\displaystyle{ \xi}\) spełnia zależność

\(\displaystyle{ \xi= \frac{1}{4+\xi}}\)

z czego wynika, że

\(\displaystyle{ \xi=-2 \pm \sqrt{5}}\)

oczywiście ten ułamek był dodatni zatem wybarwiamy dodatnią liczbę co daje \(\displaystyle{ \xi=-2+ \sqrt{5}}\) taki wynik otrzymujemy gdy tych czwórek jest nieskocznie wiele zatem

\(\displaystyle{ \lim_{n \to \infty }F_n=2+\xi=2-2+\sqrt{5}=\sqrt{5}}\)-- 19 maja 2019, o 17:56 --Ciekawostką jest to, że ta rekurencja ma jawną reprezentację

\(\displaystyle{ F_n= \sqrt{5} \cdot \left( \frac{2}{1-\left( 4 \sqrt{5}-9 \right)^n }-1 \right)}\)

Z niej też wynika natychmiast, że \(\displaystyle{ F_n \rightarrow \sqrt{5}}\)

[Premislav]

Można również skorzystać z własności homografii.
Funkcji homograficznej \(\displaystyle{ y=\frac{ax+b}{cx+d}}\) (plus jakieś minimalne założenia na \(\displaystyle{ c,d}\)) odpowiada macierz \(\displaystyle{ \left(\begin{array}{cc}a&b\\c&d\end{array}\right)}\),
a składaniu homografii odpowiada mnożenie macierzy.
U nas \(\displaystyle{ F(n)= \frac{2F(n-1)+5}{F(n-1)+2}}\), więc nasza homografia ma postać \(\displaystyle{ \frac{2x+5}{x+2}}\) i odpowiada jej macierz \(\displaystyle{ \left(\begin{array}{cc}2&5\\1&2\end{array}\right)}\)
Kolejne kroki rekurencji odpowiadają więc potęgowaniu tej macierzy. Zdiagonalizujmy ją, by wygodnie potęgować: wielomian charakterystyczny macierzy \(\displaystyle{ \left(\begin{array}{cc}2&5\\1&2\end{array}\right)}\) to \(\displaystyle{ \det\left(\begin{array}{cc}2-x&5\\1&2-x\end{array}\right)=(2-x)^2-5}\),
czyli równanie charakterystyczne ma postać \(\displaystyle{ (2-x)^2-5=0}\). Bez trudu je rozwiązujemy, dostając \(\displaystyle{ x_1=2-\sqrt{5}, \ x_2=2+\sqrt{5}}\)
To są wartości własne macierzy \(\displaystyle{ \left(\begin{array}{cc}2&5\\1&2\end{array}\right)}\)
Następnie znajdujemy odpowiadające jej wektory własne:
\(\displaystyle{ \left(\begin{array}{cc}2&5\\1&2\end{array}\right)\left(\begin{array}{c}x\\y\end{array}\right)=(2-\sqrt{5})\left(\begin{array}{c}x\\y\end{array}\right)}\)
daje nam układ równań
\(\displaystyle{ \begin{cases} 2x+5y=(2-\sqrt{5})x \\x+2y=(2-\sqrt{5})y \end{cases}}\)
z którego wychodzi, że \(\displaystyle{ y=-\frac{1}{\sqrt{5}}x}\), więc przykładowy wektor własny naszej macierzy odpowiadający wartości własnej \(\displaystyle{ x_1=2-\sqrt{5}}\) to \(\displaystyle{ \left(\begin{array}{c}\sqrt{5}\\-1\end{array}\right)}\)
Natomiast z
\(\displaystyle{ \left(\begin{array}{cc}2&5\\1&2\end{array}\right)\left(\begin{array}{c}x\\y\end{array}\right)=(2+\sqrt{5})\left(\begin{array}{c}x\\y\end{array}\right)}\)
otrzymujemy układ równań:
\(\displaystyle{ \begin{cases} 2x+5y=(2+\sqrt{5})x \\ x+2y=(2+\sqrt{5})y \end{cases}}\)
z którego dostajemy \(\displaystyle{ y=\frac{1}{\sqrt{5}}x}\),
czyli wektorem własnym naszej macierzy odpowiadającym wartości własnej \(\displaystyle{ x_2=2+\sqrt{5}}\) jest np. \(\displaystyle{ \left(\begin{array}{c}\sqrt{5}\\1\end{array}\right)}\)
Otrzymujemy więc, że
\(\displaystyle{ \left(\begin{array}{cc}2&5\\1&2\end{array}\right)=\left(\begin{array}{cc}\sqrt{5}&\sqrt{5}\\-1&1\end{array}\right)
\left(\begin{array}{cc}2-\sqrt{5}&0\\0&2+\sqrt{5}\end{array}\right)
\left(\begin{array}{cc}\sqrt{5}&\sqrt{5}\\-1&1\end{array}\right)^{-1}}\)
a nietrudno obliczyć, że
\(\displaystyle{ \left(\begin{array}{cc}\sqrt{5}&\sqrt{5}\\-1&1\end{array}\right)^{-1}=\frac{1}{2\sqrt{5}}\left(\begin{array}{cc}1&-\sqrt{5}\\1&\sqrt{5}\end{array}\right)}\)

Dostajemy zatem (można to udowodnić indukcyjnie)
\(\displaystyle{ \left(\begin{array}{cc}2&5\\1&2\end{array}\right)^n=\left(\begin{array}{cc}\sqrt{5}&\sqrt{5}\\-1&1\end{array}\right)
\left(\begin{array}{cc}(2-\sqrt{5})^n&0\\0&(2+\sqrt{5})^n\end{array}\right)
\left(\begin{array}{cc}\frac 1{2\sqrt{5}}&-\frac 1 2\\\frac1{2\sqrt{5}}&\frac 1 2\end{array}\right)}\)
Po wymnożeniu tych macierzy otrzymujemy
\(\displaystyle{ \left(\begin{array}{cc}2&5\\1&2\end{array}\right)^n=\left(\begin{array}{cc}\sqrt{5}&\sqrt{5}\\-1&1\end{array}\right) \left(\begin{array}{cc}\frac{1}{2\sqrt{5}}(2-\sqrt{5})^n&-\frac 1 2 (2-\sqrt{5})^n\\\frac{1}{2\sqrt{5}}(2+\sqrt{5})^n&\frac 1 2(2+\sqrt{5})^n\end{array}\right)=\\= \left(\begin{array}{cc}\frac{(2-\sqrt{5})^n+(2+\sqrt{5})^n}2&\frac{\sqrt{5}\left((2+\sqrt{5})^n-(2-\sqrt{5})^n\right)}2\\\frac{(2+\sqrt{5})^n-(2-\sqrt{5})^n}{2\sqrt{5}}&\frac{(2-\sqrt{5})^n+(2+\sqrt{5})^n}{2}\end{array}\right)}\)

Mamy więc (nasz ciąg jest numerowany od \(\displaystyle{ 1}\)):
\(\displaystyle{ F(n)= \frac{\frac{(2-\sqrt{5})^{n-1}+(2+\sqrt{5})^{n-1}}2F(1)+\frac{\sqrt{5}\left((2+\sqrt{5})^{n-1}-(2-\sqrt{5})^{n-1}\right)}2}{\frac{(2+\sqrt{5})^{n-1}-(2-\sqrt{5})^{n-1}}{2\sqrt{5}}F(1)+\frac{(2-\sqrt{5})^{n-1}+(2+\sqrt{5})^{n-1}}{2}}=\\= \frac{(2-\sqrt{5})^{n-1}+(2+\sqrt{5})^{n-1}+\frac{\sqrt{5}\left((2+\sqrt{5})^{n-1}-(2-\sqrt{5})^{n-1}\right)}2}{\frac{(2+\sqrt{5})^{n-1}-(2-\sqrt{5})^{n-1}}{\sqrt{5}}+\frac{(2-\sqrt{5})^{n-1}+(2+\sqrt{5})^{n-1}}{2}}}\)
i już za pomocą trywialnych przekształceń (dzielimy licznik i mianownik przez \(\displaystyle{ (2+\sqrt{5})^{n-1}}\) i korzystamy z twierdzenia o granicy ilorazu) obliczamy, że
\(\displaystyle{ \lim_{n \to \infty}F(n)=\sqrt{5}}\)
Takie rozwiązanie jest stosunkowo żmudne, ale za to dość ogólne i pozwala przejść od głupiej kombinatoryki do fajnej algebry liniowej (no, to ostatnie subiektywne akurat ).

EDIT: Poprawiłem w jednym miejscu \(\displaystyle{ n}\) na \(\displaystyle{ n-1}\), żeby nie było niejasności.

[suchy1111]

Janusz Tracz, Premislav DZIĘKUJE wam serdecznie za pomoc. Było to jedno z tych zadań które sprawiło mi nie lada problem, a dzięki wam wszystko stało się jasne. Jeszcze raz serdecznie dziękuje za pomoc !