LII OM - III - Zadanie 3

Rozważamy ciąg $ (x_n) $ określony rekurencyjnie wzorami

\[<br />
x_{1}=a,\ x_{2}=b\ \textrm{oraz}\ x_{n+2}=x_{n+1}+x_{n}\ \textrm{dla}\  n=1,2,3,\ldots,<br />
\]

gdzie $ a $ i $ b $ są liczbami rzeczywistymi.

Liczbę $ c $ będziemy nazywać wartością wielokrotną ciągu $ (x_n) $, jeżeli istnieją co najmniej dwie różne liczby całkowite dodatnie $ k $ i $ l $ takie, że $ x_k = x_l = c $. Wykazać, że można tak dobrać liczby $ a $ i $ b $, aby ciąg $ (x_n) $ miał więcej niż $ 2000 $ wartości wielokrotnych, ale nie można tak dobrać $ a $ i $ b $, aby miał on nieskończenie wiele wartości wielokrotnych.

Rozwiązanie

Ciąg $ (x_n) $ spełnia taką samą rekurencję, jak ciąg Fibonacciego

\[<br />
F_{1}=F_{2}=1,\ F_{n+2}=F_{n+1}+F_{n}\ \textrm{dla}\ n=1,2,3,\ldots.<br />
\]

Niech dodatkowo $ F_0 = 0 $ oraz $ F_{-n} = (-1)^{n+1}F_n $ dla $ n = 1,2,3,\ldots $. Wówczas równość $ F_{n+2} = F_{n+1} + F_n $ zachodzi dla dowolnej liczby całkowitej $ n $.

Przyjmijmy $ a = F_{-4001} $ oraz $ b = F_{-4000} $. Wtedy $ x_n = F_{n-4002} $. Ponadto dla $ n = 1,3,5,7,\ldots,4001 $ uzyskujemy $ x_n = F_{n-4002} = F_{4002-n} = x_{8004-n} $. Stąd wynika, że liczby $ F_1,F_3,F_5,\ldots,F_{4001} $ są wartościami wielokrotnymi ciągu $ (x_n) $; są one różne i jest ich więcej niż $ 2000 $.

Dla dowolnego ciągu $ (x_n) $ spełniającego warunek

\[<br />
x_{n+2} = x_{n+1} + x_n \  \textrm{dla}\ n = 1,2,3,\ldots<br />
\]

istnieją takie liczby rzeczywiste $ A $ i $ B $, że

\[<br />
x_{n}=A\alpha^{n}+B\beta^{n}\text{ }dla\text{ }n=1,2,3,\ldots,<br />
\]

gdzie $ \alpha=\frac{1}{2}(1+\sqrt{5}) $, $ \beta=\frac{1}{2}(1-\sqrt{5}) $ są pierwiastkami wielomianu $ x^2-x - 1 $.

Jeżeli $ A = B = 0 $, to wszystkie wyrazy ciągu $ (x_n) $ są zerami i liczba $ 0 $ jest jedyną wartością wielokrotną ciągu $ (x_n) $.

Jeżeli $ A = 0 $ oraz $ B \neq 0 $, to wszystkie wyrazy ciągu $ (x_n) $ są różne i ciąg $ (x_n) $ nie ma wartości wielokrotnych.

Jeżeli natomiast $ A \ne 0 $, to

\[<br />
\lim_{n\to \infty} x_n=\left\{\begin{array}{ll}<br />
+\infty&\textrm{gdy}\ A>0,\\<br />
-\infty&\textrm{gdy}\ A<0.<br />
\end{array}\right.<br />
\]

Zatem istnieje taka liczba naturalna $ N $, że dla wszystkich $ n \geq N $, $ x_n \ne 0 $. Ponadto

\[<br />
\frac{x_{n+1}}{x_{n}}=\frac{A\alpha^{n+1}+B\beta^{n+1}}{A\alpha^{n}+B\beta^{n}}=\frac{A\alpha+B\beta(\frac{\beta}{\alpha})^{n}}{A+B(\frac{\beta}{\alpha})^{n}}\ (n\geq N),<br />
\]

a zatem $ \lim_{n\to \infty} \frac{x_{n+1}}{x_n} =\alpha>1 $.

Stąd wynika, że ciąg $ (x_n) $ od pewnego miejsca jest rosnący i w związku z tym nie może mieć nieskończenie wielu wartości wielokrotnych.

Komentarze

Dodaj nową odpowiedź