ciąg rekurencyjny

Własności ciągów i zbieżność, obliczanie granic. Twierdzenia o zbieżności.
ann_u
Użytkownik
Użytkownik
Posty: 60
Rejestracja: 14 wrz 2018, o 18:56
Płeć: Kobieta
Lokalizacja: Brak

ciąg rekurencyjny

Post autor: ann_u » 17 wrz 2018, o 12:02

Niech ciąg będzie zdefiniowany rekurencyjnie przez \(a_1 = 1, a_2 = 7\) oraz a\(_{n+2} = 6a_{n+1}-a_{n}\)dla każdego \(n>0\) naturalnego. Wyznacz wszystkie wartości \(n\) dla których istnieje całkowite \(k\) takie że \(a_n = 2k^2+1\)
Ostatnio zmieniony 17 wrz 2018, o 12:07 przez AiDi, łącznie zmieniany 1 raz.
Powód: Pojedyncze symbole literowe także zapisujemy z użyciem LateXa.

Tulio
Użytkownik
Użytkownik
Posty: 101
Rejestracja: 3 cze 2012, o 00:37
Płeć: Mężczyzna
Lokalizacja: Lublin

Re: ciąg rekurencyjny

Post autor: Tulio » 18 wrz 2018, o 10:56

Mamy taki ciąg:

\(a_{1} = 1 \\ a_{2} = 7 \\ a_{3} = 41\)

Przy pomocy funkcji tworzących możemy zapisać ciąg w postaci jawnej:

\(a_{n} = \frac{1}{2}\left( \left( 1+\sqrt{5}\right)^{2n-1} + \left( 1-\sqrt{5}\right)^{2n-1} \right)\)

teraz

\(a_{n} = 2k^{2} + 1\)

\(\frac{1}{2}\left( \left( 1+\sqrt{5}\right)^{2n-1} + \left( 1-\sqrt{5}\right)^{2n-1} \right) = 2k^{2} + 1\)

\(\left( 1+\sqrt{5}\right)^{2n-1} + \left( 1-\sqrt{5}\right)^{2n-1}= 4k^{2} + 2\)

Zauważmy, że \(n=1, k=0\) jest poprawnym rozwiązaniem.

Zauważmy też, że dla \(k \neq 0\) mamy:

\(4k^{2} + 2 \equiv 2 \pmod{4}\)

zaś po lewej stronie mamy:

\(\frac{\left( 1+\sqrt{5}\right)^{2n}}{1+\sqrt{5}} + \frac{\left( 1-\sqrt{5}\right)^{2n}}{1-\sqrt{5}}\)

\(\frac{\left( 2 \cdot \left( 3+\sqrt{5}\right)\right)^{n} }{1+\sqrt{5}} + \frac{\left( 2 \cdot \left( 3-\sqrt{5}\right)\right)^{n} }{1-\sqrt{5}}\)

\(2^{n} \cdot \left( \frac{\left( 3+\sqrt{5}\right)^{n} }{1+\sqrt{}5} + \frac{\left( 3-\sqrt{5}\right)^{n} }{1-\sqrt{}5}\right)\)

Jednocześnie dla \(n > 1\) mamy:

\(2^{n} \cdot \left( \frac{\left( 3+\sqrt{5}\right)^{n} }{1+\sqrt{}5} + \frac{\left( 3-\sqrt{5}\right)^{n} }{1-\sqrt{}5} \right) \equiv 0 \pmod{4}\)

Co udowadnia, że nie ma innych rozwiązań.

Przekształcenie \(a_{n}\) w postać jawną zostawiam Tobie:

Jak to zrobić

zaś ja skorzystałem z tego, że ktoś już tego dokonał:

tutaj
i tutaj

i tylko przesunąłem gdyż wzór jest dla:

\(a_{0} = 1 \\ a_{1} = 7\)

PS. Skąd dostajesz takie ciekawe zadania?
Ostatnio zmieniony 18 wrz 2018, o 14:58 przez Tulio, łącznie zmieniany 2 razy.

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 14138
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Wrocław

Re: ciąg rekurencyjny

Post autor: Premislav » 18 wrz 2018, o 13:33

A dlaczegóż to
\(\frac{\left( 3+\sqrt{5}\right)^{n} }{1+\sqrt{5}} + \frac{\left( 3-\sqrt{5}\right)^{n} }{1-\sqrt{5}}\)
jest liczbą całkowitą? Moim zdaniem z tego się należy wytłumaczyć (i chyba tutaj nie można się z tego wytłumaczyć…).
Swoją drogą jak na moje oko wszystkie wyrazy tego ciągu są nieparzyste (zatem po pomnożeniu przez \(2\) będą postaci \(4m+2\) właśnie), gdyż z równania rekurencyjnego \(a_{n+2}=6a_{n+1}-a_n\) wynika, że \(a_{n+2}\equiv a_n\pmod{2}\) dla każdego \(n\), więc jakoś powątpiewam w poprawność tego rozwiązania (tj. wzór jawny wygląda OK, ale dalsze wnioskowanie z niego jak wyżej chyba jest niepoprawne).

A oto podejście bez wzorów jawnych:
niech \(b_n= \frac{a_n-1}{2}\) i pytamy, dla jakich \(n\in \NN^+\) wyrazy ciągu \((b_n)\) są kwadratami liczb całkowitych.
Mamy \(a_1=1, \ a_2=7\), czyli \(b_1=0, \ b_2=3\) (od razu odnotujmy, że \(b_1\) spełnia warunki zadania, \(b_2\) ich nie spełnia).
Ponadto
\(a_{n+2}=6a_{n+1}-a_{n} \Leftrightarrow 2b_{n+2}+1=6(2b_{n+1}+1)-(2b_{n}+1) \Leftrightarrow \\ \Leftrightarrow b_{n+2}=6b_{n+1}-b_n+2\).
Zauważmy, że nie może być \(b_n\equiv 1\pmod{3}\). Przypuśćmy nie wprost, że jest inaczej i niech \(n_0=\min\left\{ n\in \NN^+: b_n\equiv 1\pmod{3}\right\}\). Oczywiście \(n_0>2\). Mamy wówczas
\(b_{n_0}=6b_{n_0-1}-b_{n_0-2}+2\). Ponieważ \(3|6b_{n_0-1}\), więc \(-b_{n_0-2}+2\equiv 1\pmod{3}\), czyli \(b_{n_0-2}\equiv 1\pmod{3}\), sprzeczność z minimalnością \(n_0\).
Jeżeli zaś \(b_{n}\equiv 0\pmod{3}\), to \(b_{n+2}\equiv 2\pmod{3}\), czyli
\(b_{n+2}\) nie może być kwadratem liczby całkowitej. Natomiast jeśli \(b_{n}\equiv 2\pmod{3}\), to \(3 | b_{n+2}\), więc aby \(b_{n+2}\) było kwadratem, musiałoby zajść \(9|b_{n+2}\).
To jednak nie jest możliwe dla \(n>3\), gdyż wówczas
\(b_{n+2}=6b_{n+1}-b_n+2=6(6b_n-b_{n-1}+2)-b_n+2\equiv 5-b_n-6b_{n-1}\pmod{9}\)
i wystarczy rozważyć kilka prostych przypadków:
a) \(b_n\equiv 2\pmod{9}\)
b) \(b_n\equiv 5\pmod{9}\)
c) \(b_n\equiv 8\pmod{9}\)
Natomiast dla \(n=3\) też warunki zadania nie są spełnione, gdyż oczywiście \(b_3=20\) nie jest kwadratem liczby całkowitej.

Ostatecznie rzeczywiście wychodzi \(n=1\).

Tulio
Użytkownik
Użytkownik
Posty: 101
Rejestracja: 3 cze 2012, o 00:37
Płeć: Mężczyzna
Lokalizacja: Lublin

ciąg rekurencyjny

Post autor: Tulio » 18 wrz 2018, o 14:57

No przecież napisałem to co Ty - że będą parzyste. Właśnie na tym polega moje wnioskowanie, ze mamy dwie parzystości - jedna dzieli się przez cztery (\(0 \mod 4\)), a druga nie (\(2 \mod 4\)) dla dowolnego \(n > 1\). To jest istotna część mojego wnioskowania, a nie problem.

Drugi zarzut co do całkowitości sumy tych ułamków jest bardziej celny. Przyznaję... ja nie umiem tego udowodnić (chociaż podstawiając kolejne \(n\) widzimy, że są to liczby całkowite), ale jest to udowodniony fakt:

patrz tutaj

Wystarczy sprowadzić do wspólnego mianownika, wyciągnąć \(4\) z mianownika przed nawias, rozpatrzeć \(2^{n-2}\) dla każdego \(n>3\) by otrzymać wspomniany na tej stronie wzór tego ciągu:

a(n) = ((1+sqrt(5))*(3+sqrt(5))^n + (1-sqrt(5))*(3-sqrt(5))^n)/2

(brak LaTeXa tutaj celowy - gdyż właśnie tak podany wzór widnieje na tej stronie)

więc "(i chyba tutaj nie można się z tego wytłumaczyć…)" nie zachodzi.
Ostatnio zmieniony 18 wrz 2018, o 20:36 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7144
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna

Re: ciąg rekurencyjny

Post autor: kerajs » 18 wrz 2018, o 22:38

Co do ciągu, to mam trochę inaczej. Nawet wczoraj to wstawiłem, ale skasowałem gdyż nie odpowiadało na pytanie o k.
\(x^2-6x+1=0\\ x_1= 3-2 \sqrt{2} \vee x_2=3+2 \sqrt{2} \\ a_n=A( 3-2 \sqrt{2})^{n}+B(3+2 \sqrt{2} )^{n}\)
\(\begin{cases} 1=A( 3-2 \sqrt{2})^1+B(3+2 \sqrt{2} )^1 \\ 7=A( 3-2 \sqrt{2})^2+B(3+2 \sqrt{2} )^2 \end{cases}\)
\(a_n= \frac{-1- \sqrt{2} }{2} ( 3-2 \sqrt{2})^{n}+\frac{-1+ \sqrt{2} }{2}(3+2 \sqrt{2} )^{n}\)

ODPOWIEDZ