Granica ciągu rekurencyjnego

[xdominika]

Obliczyć granicę
\(\displaystyle{ a_{1}=1; a_{n+1}=1+\frac{1}{a_{n}}}\)

\(\displaystyle{ a_{1}=0; a_{2}=1; a_{n+1}=\frac{a_{n}+a_{n-1}}{2}}\)

[Premislav]

Lepiej zapisane, ale nadal słabo.
1) \(\displaystyle{ a_{1}=1, \ a_{n+1}=1+\frac{1}{a_{n}}}\).
Zapiszmy to równanie rekurencyjne w postaci
\(\displaystyle{ a_{n+1}=\frac{a_{n}+1}{a_{n}}}\). Mamy więc równanie postaci \(\displaystyle{ a_{n+1}=f(a_{n})}\), gdzie \(\displaystyle{ f(x)=\frac{x+1}{x}}\) jest homografią. Możemy ją reprezentować poprzez macierz \(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)}\), natomiast składaniu homografii odpowiada mnożenie macierzy, a widzimy, że dla \(\displaystyle{ n\ge 2}\) jest
\(\displaystyle{ a_{n+1}=f(a_{n})=f(f(a_{n-1}))}\), i tak dalej, ogólnie \(\displaystyle{ a_{n+1}=f^{n}(a_{1})}\), gdzie \(\displaystyle{ f^{n}}\) to \(\displaystyle{ n}\)-krotne złożenie funkcji \(\displaystyle{ f}\) (z samą sobą).
Otrzymamy zatem
\(\displaystyle{ a_{n+1}=\frac{x_{11}^{(n)}\cdot a_{1}+x_{12}^{(n)}}{x_{21}^{(n)}\cdot a_{1}+x_{22}^{(n)}}}\),
gdzie \(\displaystyle{ x_{ij}^{(n)}}\) są współczynnikami macierzy \(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n}}\). Normalnie coś takiego wygodnie potęguje się dzięki diagonalizacji lub postaci Jordana i warto to znać, ale tutaj prościej byłoby udowodnić, że dla \(\displaystyle{ n\in \NN^{+}}\) mamy
\(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n}=\left(\begin{array}{cc}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{array}\right)}\),
gdzie \(\displaystyle{ F_{k}}\) jest \(\displaystyle{ k}\)-tym wyrazem ciągu Fibonacciego.
Zrobimy to indukcyjnie. Dla \(\displaystyle{ n=1}\) jest to jasne, wszak \(\displaystyle{ F_{2}=F_{1}=1, \ F_{1}=0}\).
Teraz krok indukcyjny. Przypuśćmy, że dla pewnego \(\displaystyle{ n\in \NN^{+}}\) zachodzi \(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n}=\left(\begin{array}{cc}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{array}\right)}\).
Wówczas mamy
\(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n+1}=\left(\begin{array}{cc}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{array}\right)\cdot \left(\begin{array}{cc}1&1\\1&0\end{array}\right)=\left(\begin{array}{cc}F_{n+1}+F_{n}&F_{n+1}\\F_{n}+F_{n-1}&F_{n} \end{array}\right)=\left(\begin{array}{cc}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n} \end{array}\right)}\)
a to kończy nasz dowód indukcyjny.
Czyli \(\displaystyle{ x_{11}^{(n)}=F_{n+1}, \ x_{12}^{(n)}=x_{21}^{(n)}=F_{n}, \ x_{22}^{(n)}=F_{n-1}, \ n=1,2\ldots }\)
Skoro \(\displaystyle{ a_{1}=1}\), to dostajemy
\(\displaystyle{ a_{n+1}=\frac{F_{n+1}+F_{n}}{F_{n}+F_{n-1}}}\).
Znany jest fakt (można go udowodnić na przykład z użyciem funkcji tworzących lub również za pomocą indukcji, tylko o trochę innym schemacie), że
\(\displaystyle{ F_{n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right)}\)
Ponieważ \(\displaystyle{ \frac{1+\sqrt{5}}{2}>1, \ \left|\frac{1-\sqrt{5}}{2} \right|<1}\), więc z powyższej równości nietrudno wywnioskować, że
\(\displaystyle{ \lim_{n\to \infty}F_{n}=+\infty, \ \lim_{n\to \infty}\frac{F_{n+1}}{F_{n}}=\frac{1+\sqrt{5}}{2}}\), możemy też przepisać
\(\displaystyle{ a_{n+1}=\frac{\frac{F_{n+1}}{F_{n}}+1}{1+\frac{F_{n-1}}{F_{n}}}}\)
i korzystając z powyższych własności, łatwo już uzyskujemy
\(\displaystyle{ \lim_{n\to \infty}a_{n}=\lim_{n\to \infty}a_{n+1}=\frac{\frac{1+\sqrt{5}}{2}+1}{1+\frac{1}{\frac{1+\sqrt{5}}{2}}}\\=\frac{\frac{1+\sqrt{5}}{2}+1}{1+\frac{\sqrt{5}-1}{2}}=\frac{3+\sqrt{5}}{1+\sqrt{5}}}\)

Dodano po 38 minutach 18 sekundach:
Re: Granica ciągu rekurencyjnego
2) Myślałem nad bardziej eleganckim pomysłem, ale coś chyba nie w formie jestem (jak zwykle ).
Równanie charakterystyczne odpowiadające równaniu rekurencyjnemu
\(\displaystyle{ a_{n+1}=\frac{a_{n}+a_{n-1}}{2}}\) ma postać
\(\displaystyle{ x^{2}=\frac{1}{2}x+\frac{1}{2}}\), toteż łatwo wyliczyć miejsca zerowe
\(\displaystyle{ x_{1}=1, \ x_{2}=-\frac{1}{2}}\) i w związku z tym istnieją takie stałe \(\displaystyle{ C_{1}, \ C_{2}}\), że
\(\displaystyle{ a_{n}=C_{1}\cdot 1^{n}+C_{2}\cdot \left(-\frac{1}{2}\right)^{n}}\)
Podstawiając kolejno \(\displaystyle{ n=0, \ n=1}\) otrzymujemy układ równań:
\(\displaystyle{ \begin{cases}C_{1}+C_{2}=0\\C_{1}-\frac{1}{2}C_{2}=1\end{cases}}\),
z którego to łatwo dostajemy
\(\displaystyle{ C_{1}=\frac{2}{3}, \ C_{2}=-\frac{2}{3}}\). Otrzymaliśmy więc
\(\displaystyle{ a_{n}=\frac{2}{3}-\frac{2}{3}\cdot \left(-\frac{1}{2}\right)^{n}}\), stąd oczywiście
\(\displaystyle{ \lim_{n\to \infty}a_{n}=\frac{2}{3}}\).

[a4karo]

W 2) rozpatrzmy ciąg \(b_n={a_n-a_{n-1}}\).
Ten ciąg spełnia warunek \(b_{n+1}=-b_n/2\) jest więc ciągiem geometrycznym o ilorazie \(-1/2\) i \(b_1=1\), stąd \(b_n=\frac{(-1)^{n}}{2^n}\).
Żeby wyliczyć \(a_n\) wystarczy zauważyć, że
\(\displaystyle{ b_n+b_{n-1}+\dots+b_1={a_n-a_0}}\)

Dodano po 22 minutach 52 sekundach:
A pierwsze można tak:
\(a_{n+2}=1+\frac{1}{1+\frac{1}{a_n}}\)

Oznaczmy \(\phi=\frac{\sqrt5 + 1}{2}\) i \(\phi'=\frac{\sqrt5 -1}{2}\) zauważmy, że \(\phi'=1/\phi\).

Jeżeli \(1<a_n<\phi\), to \(1+\frac{1}{a_n}>1+\phi'=\phi\), więc \(1<a_{n+2}<1+\phi'=\phi\).
Ponadto \(a_{n+2}-a_n=\frac{1+a_n-a_n^2}{1+a_n}>0\)
Ciąg parzystych iteracji jest zatem ograniczony i rosnący. Podobnie pokazujemy, że ciąg iteracji nieparzystych jest malejący i ograniczony z dołu przez \(\phi\), i łatwo wyliczyć granicę.

Dodano po 1 godzinie 50 minutach 47 sekundach:
A jeszcze prościej tak
\(\displaystyle{ a_{n+1}-\phi=1+\frac{1}{a_n}-\phi=\frac{1}{a_n}-\phi'=\frac{1}{a_n}-\frac{1}{\phi}=\frac{\phi-a_n}{\phi a_n}}\)
skąd widac od razu dwie rzeczy:
1. kolejne wyrazy ciągu leżą po przeciwnych stronach liczby \(\phi\)
2. Ciąg zbiega do \(\phi\) bo wszystkie wyrazy są nie mniejsze od \(1\) i
$$|a_{n+1}-\phi|=\frac{|\phi-a_n|}{\phi a_n}<\frac{|\phi-a_n|}{\phi }<\dots<\frac{|\phi-a_1|}{\phi^n}$$

[xdominika]

Lepiej zapisane, ale nadal słabo.
1) \(\displaystyle{ a_{1}=1, \ a_{n+1}=1+\frac{1}{a_{n}}}\).
Zapiszmy to równanie rekurencyjne w postaci
\(\displaystyle{ a_{n+1}=\frac{a_{n}+1}{a_{n}}}\). Mamy więc równanie postaci \(\displaystyle{ a_{n+1}=f(a_{n})}\), gdzie \(\displaystyle{ f(x)=\frac{x+1}{x}}\) jest homografią. Możemy ją reprezentować poprzez macierz \(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)}\), natomiast składaniu homografii odpowiada mnożenie macierzy, a widzimy, że dla \(\displaystyle{ n\ge 2}\) jest
\(\displaystyle{ a_{n+1}=f(a_{n})=f(f(a_{n-1}))}\), i tak dalej, ogólnie \(\displaystyle{ a_{n+1}=f^{n}(a_{1})}\), gdzie \(\displaystyle{ f^{n}}\) to \(\displaystyle{ n}\)-krotne złożenie funkcji \(\displaystyle{ f}\) (z samą sobą).
Otrzymamy zatem
\(\displaystyle{ a_{n+1}=\frac{x_{11}^{(n)}\cdot a_{1}+x_{12}^{(n)}}{x_{21}^{(n)}\cdot a_{1}+x_{22}^{(n)}}}\),
gdzie \(\displaystyle{ x_{ij}^{(n)}}\) są współczynnikami macierzy \(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n}}\). Normalnie coś takiego wygodnie potęguje się dzięki diagonalizacji lub postaci Jordana i warto to znać, ale tutaj prościej byłoby udowodnić, że dla \(\displaystyle{ n\in \NN^{+}}\) mamy
\(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n}=\left(\begin{array}{cc}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{array}\right)}\),
gdzie \(\displaystyle{ F_{k}}\) jest \(\displaystyle{ k}\)-tym wyrazem ciągu Fibonacciego.
Zrobimy to indukcyjnie. Dla \(\displaystyle{ n=1}\) jest to jasne, wszak \(\displaystyle{ F_{2}=F_{1}=1, \ F_{1}=0}\).
Teraz krok indukcyjny. Przypuśćmy, że dla pewnego \(\displaystyle{ n\in \NN^{+}}\) zachodzi \(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n}=\left(\begin{array}{cc}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{array}\right)}\).
Wówczas mamy
\(\displaystyle{ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n+1}=\left(\begin{array}{cc}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{array}\right)\cdot \left(\begin{array}{cc}1&1\\1&0\end{array}\right)=\left(\begin{array}{cc}F_{n+1}+F_{n}&F_{n+1}\\F_{n}+F_{n-1}&F_{n} \end{array}\right)=\left(\begin{array}{cc}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n} \end{array}\right)}\)
a to kończy nasz dowód indukcyjny.
Czyli \(\displaystyle{ x_{11}^{(n)}=F_{n+1}, \ x_{12}^{(n)}=x_{21}^{(n)}=F_{n}, \ x_{22}^{(n)}=F_{n-1}, \ n=1,2\ldots }\)
Skoro \(\displaystyle{ a_{1}=1}\), to dostajemy
\(\displaystyle{ a_{n+1}=\frac{F_{n+1}+F_{n}}{F_{n}+F_{n-1}}}\).
Znany jest fakt (można go udowodnić na przykład z użyciem funkcji tworzących lub również za pomocą indukcji, tylko o trochę innym schemacie), że
\(\displaystyle{ F_{n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right)}\)
Ponieważ \(\displaystyle{ \frac{1+\sqrt{5}}{2}>1, \ \left|\frac{1-\sqrt{5}}{2} \right|<1}\), więc z powyższej równości nietrudno wywnioskować, że
\(\displaystyle{ \lim_{n\to \infty}F_{n}=+\infty, \ \lim_{n\to \infty}\frac{F_{n+1}}{F_{n}}=\frac{1+\sqrt{5}}{2}}\), możemy też przepisać
\(\displaystyle{ a_{n+1}=\frac{\frac{F_{n+1}}{F_{n}}+1}{1+\frac{F_{n-1}}{F_{n}}}}\)
i korzystając z powyższych własności, łatwo już uzyskujemy
\(\displaystyle{ \lim_{n\to \infty}a_{n}=\lim_{n\to \infty}a_{n+1}=\frac{\frac{1+\sqrt{5}}{2}+1}{1+\frac{1}{\frac{1+\sqrt{5}}{2}}}\\=\frac{\frac{1+\sqrt{5}}{2}+1}{1+\frac{\sqrt{5}-1}{2}}=\frac{3+\sqrt{5}}{1+\sqrt{5}}}\)

A czy można to zrobić w jakiś inny sposób? Niestety nie miałam jeszcze takich działań na macierzach. Kiedy wypisałam sobie kilka pierwszych wyrazów ciągu \(\displaystyle{ a_{n}}\) zauważyłam, że jest on w postaci \(\displaystyle{ \frac{F_{n+1}}{F_{n}}}\), czy jest to prawidłowe rozumowanie?

[a4karo]

Jak to zauważyłaś, to udowodnij to indukcją

[xdominika]

Jak to zauważyłaś, to udowodnij to indukcją

Właśnie to już niestety mi nie wychodzi

[a4karo]

A pokaż jakąś próbę?

Dodano po 1 minucie 37 sekundach:
Wiesz jaką rekurencje spełniają liczby Fibonacciego?

[xdominika]

A pokaż jakąś próbę?

Dodano po 1 minucie 37 sekundach:
Wiesz jaką rekurencje spełniają liczby Fibonacciego?

Wiem, że \(\displaystyle{ F_{1}=1}\), \(\displaystyle{ F_{2}=1}\), \(\displaystyle{ F_{n+1}= F_{n}+ F_{n-1} }\) oraz że \(\displaystyle{ F_{n}= \frac{1}{ \sqrt{5} }\left( \left( \frac{1+ \sqrt{5} }{2} \right) ^{2}-\left( \frac{1- \sqrt{5} }{2} \right) ^{2} \right) }\)

[a4karo]

No to indukcja idzie automatycznie. Po prostu napisz wzór. (nie ten wielki, który błędnie przepisałas)

[janusz47]

Sprawdzamy, że ciąg \(\displaystyle{ a_{1} = 1, \ \ a_{n+1} = 1 + \frac{1}{a_{n}} }\) jest ciągiem Cauchy'ego

\(\displaystyle{ (a_{n}) = ( a_{1}, a_{2}, a_{3}, a_{4},...) = \left( 1, 2, \frac{3}{2}, \frac{5}{3}, ...\right) }\)

\(\displaystyle{ \bigwedge(\varepsilon >0) \bigvee(p\in \NN) \left( \bigvee n, m \in \NN \right ) (m, n > p) \rightarrow |a_{n} - a_{m}| < \varepsilon }\)

\(\displaystyle{ a_{n+1} - a_{n} = \left( 1 +\frac{1}{a_{n}}\right) - \left( 1 + \frac{1}{a_{n-1}} \right) = \frac{1}{a_{n}} - \frac{1}{a_{n-1}} = \frac{a_{n-1} - a_{n}}{a_{n}\cdot a_{n-1}} = 0 }\)

Ciąg \(\displaystyle{ (a_{n}) }\) ma granicę \(\displaystyle{ g > 0. }\)

Niech \(\displaystyle{ \lim_{n\to \infty} a_{n} = g = \lim_{n\to \infty} a_{n+1} }\)

Wtedy \(\displaystyle{ g = 1 + \frac{1}{g} }\)

\(\displaystyle{ g^2 -g -1 = 0 }\)

\(\displaystyle{ g = \frac{1 + \sqrt{5}}{2} }\) (złota liczba - liczba złotego podziału odcinka)

Można udowodnić w oparciu o indukcję czy wzory Bineta , Cassiniego, że ciąg

\(\displaystyle{ (a_{n}) = \left(\frac{F_{n+1}}{F_{n}}\right), }\) gdzie \(\displaystyle{ (F_{n}) }\) jest ciągiem Fibonacci.

[a4karo]

Sprawdzamy, że ciąg \(\displaystyle{ a_{1} = 1, \ \ a_{n+1} = 1 + \frac{1}{a_{n}} }\) jest ciągiem Cauchy'ego

\(\displaystyle{ (a_{n}) = ( a_{1}, a_{2}, a_{3}, a_{4},...) = \left( 1, 2, \frac{3}{2}, \frac{5}{3}, ...\right) }\)

\(\displaystyle{ \bigwedge(\varepsilon >0) \bigvee(p\in \NN) \left( \bigvee n, m \in \NN \right ) (m, n > p) \rightarrow |a_{n} - a_{m}| < \varepsilon }\)

\(\displaystyle{ a_{n+1} - a_{n} = \left( 1 +\frac{1}{a_{n}}\right) - \left( 1 + \frac{1}{a_{n-1}} \right) = \frac{1}{a_{n}} - \frac{1}{a_{n-1}} = \frac{a_{n-1} - a_{n}}{a_{n}\cdot a_{n-1}} = 0 }\)

Janusz, już jest bardzo późno. Wyśpij się.

Dodano po 19 minutach 34 sekundach:
Przecież indukcja jest banalna: skoro \(a_n=\frac{F_{n+1}}{F_n}\), to
$$a_{n+1}=1+\frac{1}{a_n}=1+\frac{1}{\frac{F_{n+1}}{F_n}}=1+\frac{F_n}{F_{n+1}}=\frac{F_{n+1}+F_n}{F_{n+1}}=\frac{F_{n+2}}{F_{n+1}}$$

[xdominika]

Przecież indukcja jest banalna: skoro \(a_n=\frac{F_{n+1}}{F_n}\), to
$$a_{n+1}=1+\frac{1}{a_n}=1+\frac{1}{\frac{F_{n+1}}{F_n}}=1+\frac{F_n}{F_{n+1}}=\frac{F_{n+1}+F_n}{F_{n+1}}=\frac{F_{n+2}}{F_{n+1}}$$

Właśnie już wpadłam jak to zrobić, rzeczywiście bardzo proste, ale już tak mam, że często mam problem z prostymi, a nie trudnymi zadaniami, dziękuję bardzo za pomoc

[janusz47]

Można też zastosować rozwinięcie ciągu w ułamek łańcuchowy

\(\displaystyle{ a = \lim_{n\to \infty} a_{n} = 1 +\frac{1}{1 + \frac{1}{ 1 + \frac{1}{1+...}}} }\)

\(\displaystyle{ a = 1 + \frac{1}{a} }\)

\(\displaystyle{ a^2 - a - 1 = 0 }\)

\(\displaystyle{ a = \frac{1 +\sqrt{5}}{2} }\)

[a4karo]

Tylko najpierw trzeba pokazać jego zbieżność