Rekurencja

[Nadine]

Niech \(\displaystyle{ (x_n)_{n≥1} }\) będzie ciągiem zdefiniowanym rekurencyjnie:
\(\displaystyle{ x_1 = 1, x_{n+1} = 1 + 1 \frac{1}{x_n} }\)
Udowodnij, że dla dowolnych \(\displaystyle{ m, n ∈ \NN^+}\) zachodzi
\(\displaystyle{ x_{m+n}= \frac{2+x_m x_n}{x_m + x_n} }\)
Czy próba zrobienia tego indukcją matematyczną jest dobrym pomysłem?

[kerajs]

Łatwo zauważyć że :
\(\displaystyle{ x_n= \frac{F_{n+1}}{F_n} }\)
Gdzie wzór jawny na liczby Fibonacciego to: \(\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] }\)
Przypuszczam, że wystarczy pobawić się własnościami tych liczb aby udowodnić zadaną tożsamość.

[Nadine]

A bez ciągów Fibonacciego, bo chyba nie rozumiem

[Premislav]

Przepraszam za spam, ale co ma znaczyć \(\displaystyle{ 1\frac{1}{x_{n}}}\) Chyba długo myślano nad tym, jak zastosować najbardziej niejednoznaczny zapis.

[kerajs]

Hmm..., mam wrażenie że przed poprawą tematu zapis rekurencji był ciut inny.
Moja odpowiedź dotyczyła ciągu: \(\displaystyle{ x_1=1 \ \wedge x_{n+1}=1+ \frac{1}{x_n}}\) co faktycznie daje \(\displaystyle{ x_n= \frac{F_{n+1}}{F_n}}\) . Ponadto wtedy, skoro podałem dwie drogi wykazania tezy, byłem zbyt leniwy aby dalej rozwiązywać zadanko.


Jednak teraz widzę, że dla takiego ciągu teza nie jest prawdziwa, więc może coś zostało niepoprawnie przepisane.

[Jan Kraszewski]

Hmm..., mam wrażenie że przed poprawą tematu zapis rekurencji był ciut inny.

Czyżbym coś zepsuł edytując? Nie twierdzę, że to niemożliwe.

JK

[Premislav]

Może trochę reverse engineering:
w równości z tezy połóżmy \(\displaystyle{ m:=1}\), a otrzymamy zależność
\(\displaystyle{ x_{n+1}=\frac{2+x_{1}x_{n}}{x_{1}+x_{n}}}\)
i korzystając z warunku początkowego \(\displaystyle{ x_{1}=1}\), który wygląda na niezepsuty, dostajemy
\(\displaystyle{ x_{n+1}=\frac{2+x_{n}}{1+x_{n}}=\red{1+\frac{1}{1+x_{n}}}}\). Czyli zachodzi uzasadnione podejrzenie, że miało być tak:
\(\displaystyle{ \blue{x_{1}=1, \ x_{n+1}=1+\frac{1}{1+x_{n}}}}\).
Przy tak postawionej sprawie dowód tezy zadania to prosta indukcja po \(\displaystyle{ m\in \NN}\) przy ustalonym \(\displaystyle{ n\in \NN}\).
Dla \(\displaystyle{ m=1}\) dostajemy dokładnie
\(\displaystyle{ x_{n+1}=\frac{2+x_{1}x_{n}}{x_{1}+x_{n}}=\frac{2+x_{n}}{1+x_{n}}=1+\frac{1}{1+x_{n}}}\). Dalej przypuśćmy, że dla pewnego \(\displaystyle{ m\in \NN, \ m\ge 1}\) zachodzi
\(\displaystyle{ x_{m+n}=\frac{2+x_{m}x_{n}}{x_{m}+x_{n}}}\). Korzystając z „niebieskiego' warunku, dostajemy wówczas
\(\displaystyle{ x_{(m+1)+n}=x_{(m+n)+1}=1+\frac{1}{1+x_{m+n}}}\), następnie z założenia indukcyjnego mamy
\(\displaystyle{ x_{m+n}=\frac{2+x_{m}x_{n}}{x_{m}+x_{n}}}\), toteż
\(\displaystyle{ x_{(m+1)+n}=1+\frac{1}{1+x_{m+n}}=1+\frac{1}{1+\frac{2+x_{m}x_{n}}{x_{m}+x_{n}}}\\=1+\frac{x_{m}+x_{n}}{2+x_{m}x_{n}+x_{m}+x_{n}}=\frac{2+x_{m}x_{n}+2(x_{m}+x_{n})}{2+x_{m}x_{n}+x_{m}+x_{n}}}\)
i pozostaje wykazać, że
\(\displaystyle{ \frac{2+x_{m}x_{n}+2(x_{m}+x_{n})}{2+x_{m}x_{n}+x_{m}+x_{n}}=\frac{2+x_{m+1}x_{n}}{x_{m+1}+x_{n}}}\).
W tym celu korzystamy z zależności rekurencyjnej, by otrzymać
\(\displaystyle{ x_{m+1}=1+\frac{1}{1+x_{m}}}\) i mamy
\(\displaystyle{ P=\frac{2+x_{m+1}x_{n}}{x_{m+1}+x_{n}}=\frac{2+x_{n}+\frac{x_{n}}{1+x_{m}}}{1+\frac{1}{1+x_{m}}+x_{n}}\\=\frac{2+2x_{m}+2x_{n}+x_{m}x_{n}}{2+x_{m}+x_{n}+x_{m}x_{n}}=L}\)
a to kończy dowód.

[kerajs]

Można także bez indukcji. Np:
Ciąg \(\displaystyle{ x_n=1+ \frac{1}{1+x_{n-1}} }\) jest równoważny ciągowi \(\displaystyle{ x_n= \frac{a_n}{b_n} }\) gdzie
\(\displaystyle{ \begin{cases} a_n=b_{n-1}+b_n \\ b_n=a_{n-1}+b_{n-1} \end{cases}}\)
rozwiązaniem powyższego układu rekurencji jest:
\(\displaystyle{ \begin{cases} a_n= \frac{1}{2}\left[ \left( 1+ \sqrt{2} \right)^n+\left( 1- \sqrt{2} \right)^n \right] \\ b_n= \frac{1}{2 \sqrt{2} }\left[ \left( 1+ \sqrt{2} \right)^n-\left( 1- \sqrt{2} \right)^n \right] \end{cases} }\)
i stąd:
\(\displaystyle{ x_n= \sqrt{2} \frac{\left( 1+ \sqrt{2} \right)^n+\left( 1- \sqrt{2} \right)^n}{\left( 1+ \sqrt{2} \right)^n-\left( 1- \sqrt{2} \right)^n} }\).
Przypuszczam, że znając wzór jawny, wykazanie tezy nie powinno być dużym problemem.

Dodano po 54 minutach 18 sekundach:
\(\displaystyle{ P= \frac{2+x_mx_n}{x_m+x_n}= \frac{2+ \sqrt{2} \frac{\left( 1+ \sqrt{2} \right)^m+\left( 1- \sqrt{2} \right)^m}{\left( 1+ \sqrt{2} \right)^m-\left( 1- \sqrt{2} \right)^m} \sqrt{2} \frac{\left( 1+ \sqrt{2} \right)^n+\left( 1- \sqrt{2} \right)^n}{\left( 1+ \sqrt{2} \right)^n-\left( 1- \sqrt{2} \right)^n} }{ \sqrt{2} \frac{\left( 1+ \sqrt{2} \right)^m+\left( 1- \sqrt{2} \right)^m}{\left( 1+ \sqrt{2} \right)^m-\left( 1- \sqrt{2} \right)^m}+ \sqrt{2} \frac{\left( 1+ \sqrt{2} \right)^n+\left( 1- \sqrt{2} \right)^n}{\left( 1+ \sqrt{2} \right)^n-\left( 1- \sqrt{2} \right)^n} } =
\sqrt{2 } \frac{1+ \frac{\left( 1+ \sqrt{2} \right)^m+\left( 1- \sqrt{2} \right)^m}{\left( 1+ \sqrt{2} \right)^m-\left( 1- \sqrt{2} \right)^m} \frac{\left( 1+ \sqrt{2} \right)^n+\left( 1- \sqrt{2} \right)^n}{\left( 1+ \sqrt{2} \right)^n-\left( 1- \sqrt{2} \right)^n} }{ \frac{\left( 1+ \sqrt{2} \right)^m+\left( 1- \sqrt{2} \right)^m}{\left( 1+ \sqrt{2} \right)^m-\left( 1- \sqrt{2} \right)^m}+ \frac{\left( 1+ \sqrt{2} \right)^n+\left( 1- \sqrt{2} \right)^n}{\left( 1+ \sqrt{2} \right)^n-\left( 1- \sqrt{2} \right)^n} }=\\
\\
= \sqrt{2} \frac{\left(\left( 1+ \sqrt{2} \right)^m-\left( 1- \sqrt{2} \right)^m \right)\left( \left( 1+ \sqrt{2} \right)^n-\left( 1- \sqrt{2} \right)^n\right) +\left( \left( 1+ \sqrt{2} \right)^m+\left( 1- \sqrt{2} \right)^m\right)\left( \left( 1+ \sqrt{2} \right)^n+\left( 1- \sqrt{2} \right)^n\right) }{\left( \left( 1+ \sqrt{2} \right)^m+\left( 1- \sqrt{2} \right)^m\right)\left( \left( 1+ \sqrt{2} \right)^n-\left( 1- \sqrt{2} \right)^n\right)+\left( \left( 1+ \sqrt{2} \right)^n+\left( 1- \sqrt{2} \right)^n\right)\left( \left( 1+ \sqrt{2} \right)^m-\left( 1- \sqrt{2} \right)^m\right)} =\\
= \sqrt{2} \frac{2\left( 1+ \sqrt{2} \right)^m\left( 1+ \sqrt{2} \right)^n+2\left( 1- \sqrt{2} \right)^m\left( 1- \sqrt{2} \right)^n}{2\left( 1+ \sqrt{2} \right)^m\left( 1+ \sqrt{2} \right)^n-2\left( 1- \sqrt{2} \right)^m\left( 1- \sqrt{2} \right)^n} = \sqrt{2} \frac{\left( 1+ \sqrt{2} \right)^{m+n}+\left( 1-\sqrt{2} \right)^{m+n}}{\left( 1+ \sqrt{2} \right)^{m+n}-\left( 1-\sqrt{2} \right)^{m+n}} =x_{n+m}=L}\)