LII OM - III - Zadanie 3

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

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

$ x_{1}=a,\ x_{2}=b\ \textrm{oraz}\ x_{n+2}=x_{n+1}+x_{n}\ \textrm{dla}\ n=1,2,3,\ldots, $

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

$ F_{1}=F_{2}=1,\ F_{n+2}=F_{n+1}+F_{n}\ \textrm{dla}\ n=1,2,3,\ldots. $

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

$ x_{n+2} = x_{n+1} + x_n \ \textrm{dla}\ n = 1,2,3,\ldots $

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

$ x_{n}=A\alpha^{n}+B\beta^{n}\text{ }dla\text{ }n=1,2,3,\ldots, $

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

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

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

$ \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), $

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.