ciąg rekurencyjny

[ann_u]

Niech ciąg będzie zdefiniowany rekurencyjnie przez \(\displaystyle{ a_1 = 1, a_2 = 7}\) oraz a\(\displaystyle{ _{n+2} = 6a_{n+1}-a_{n}}\)dla każdego \(\displaystyle{ n>0}\) naturalnego. Wyznacz wszystkie wartości \(\displaystyle{ n}\) dla których istnieje całkowite \(\displaystyle{ k}\) takie że \(\displaystyle{ a_n = 2k^2+1}\)

[Tulio]

Mamy taki ciąg:

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

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

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

teraz

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

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

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

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

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

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

zaś po lewej stronie mamy:

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

\(\displaystyle{ \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}}}\)

\(\displaystyle{ 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 \(\displaystyle{ n > 1}\) mamy:

\(\displaystyle{ 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 \(\displaystyle{ a_{n}}\) w postać jawną zostawiam Tobie:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Funkcja_tworz%C4%85ca

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


[url=http://mathworld.wolfram.com/NSWNumber.html]i tutaj[/url]

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

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

PS. Skąd dostajesz takie ciekawe zadania?

[Premislav]

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

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

[Tulio]

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 (\(\displaystyle{ 0 \mod 4}\)), a druga nie (\(\displaystyle{ 2 \mod 4}\)) dla dowolnego \(\displaystyle{ 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 \(\displaystyle{ n}\) widzimy, że są to liczby całkowite), ale jest to udowodniony fakt:

Kod: Zaznacz cały

https://oeis.org/search?q=1%2C+8%2C+44%2C+232%2C+1216&sort=&language=english&go=Search

Wystarczy sprowadzić do wspólnego mianownika, wyciągnąć \(\displaystyle{ 4}\) z mianownika przed nawias, rozpatrzeć \(\displaystyle{ 2^{n-2}}\) dla każdego \(\displaystyle{ 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.

[kerajs]

Co do ciągu, to mam trochę inaczej. Nawet wczoraj to wstawiłem, ale skasowałem gdyż nie odpowiadało na pytanie o k.
\(\displaystyle{ 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}}\)
\(\displaystyle{ \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}}\)
\(\displaystyle{ a_n= \frac{-1- \sqrt{2} }{2} ( 3-2 \sqrt{2})^{n}+\frac{-1+ \sqrt{2} }{2}(3+2 \sqrt{2} )^{n}}\)