LX OM - I - Zadanie 7

Ciąg liczb całkowitych $ f_0, f_1, f_2, \cdots $ jest określony
przez warunki: $ f_0 = 0, f_1 = 1 $,

\[<br /> (1) \qquad f_n = f_{n-1} + f_{n-2} \text{ dla } n =2,3,4, \cdots.<br /> \]

Znaleźć wszystkie wielomiany W o współczynnikach całkowitych,
mające następującą własność: Dla każdego $ n =0, 1, 2, \cdots $
istnieje taka liczba całkowita $ k $, że $ W(k)= f_n $.

Rozwiązanie

Odpowiedź: $ W(x)= \varepsilon x+c $, gdzie $ \varepsilon \in \{-1,1\} $
oraz $ c $ jest liczbą całkowitą.

Skorzystamy wielokrotnie z następującego faktu: jeżeli $ F $
jest wielomianem o współczynnikach całkowitych, to dla dowolnych
różnych liczb całkowitych $ u, v $ spełniona jest podzielność
$ u-v|F(u)-F (v) $.

Dla dowodu tego faktu wystarczy zauważyć, że jeżeli $ F(x) $
jest sumą jednomianów postaci $ a_mx^m $, gdzie współczynniki
$ a_m $ są całkowite, to różnica $ F(u)-F(v) $ jest sumą wyrażeń
postaci $ a_m(u^m - v^m) $, a każda liczba postaci $ u^m -v^m $
jest podzielna przez $ u - v $.

Ponadto będziemy stosować następujące własności ciągu
$ f_0, f_1, f_2, \cdots $:

  1. Liczby $ f_1, f_2, f_3, \cdots $ są dodatnie.
  2. Ciąg $ f_2, f_3, f_4, \cdots $ jest ściśle rosnący.
  3. Dla $ n =2,3,4, \cdots $ zachodzi nierówność
    $ f_{n-1} \geqslant \frac{1}{2} f_n $.
  4. Dla $ n =4,5,6, \cdots $ zachodzi nierówność
    $ f_{n+1} < 3f_{n-1} $.

Rzeczywiście, własność 1. jest oczywista i pociąga za sobą
własność 2., gdyż dla $ n \geqslant 3 $ mamy $ f_{n-2} > 0 $,
co daje $ f_n = f_{n-1} + f_{n-2} > f_{n-1} $. Wreszcie własności
3. i 4. wynikają z własności 2., na mocy wzoru (1) mamy bowiem
$ 2f_{n-1} \geqslant f_{n-1} + f_{n-2} = f_n $ dla $ n \geqslant 2 $
oraz

\[<br /> f_{n+1} = f_n +f_{n-1} =2f_{n-1} +f_{n-2} < 2f_{n-1} +f_{n-1}<br /> =3f_{n-1} \text{ dla } n \geqslant 4.<br /> \]

Przechodzimy do zasadniczej części rozwiązania.

Niech $ W $ będzie wielomianem spełniającym warunki zadania.
Istnieje więc liczba całkowita $ a $, dla której $ W(a)= f_0 = 0 $,
oraz liczba całkowita $ b $, dla której $ W(b)= f_1 = 1 $.
Na podstawie sformułowanego wyżej faktu różnica $ W(b)-W(a) = 1 $
jest podzielna przez $ b-a $. Stąd wniosek, że $ b-a = \pm 1 $, czyli
$ b = a+\varepsilon $, gdzie $ \varepsilon \in \{1,-1\} $. W tej
sytuacji wielomian $ P $ określony wzorem

\[<br /> (2) \qquad P(x)= W (a+\varepsilon x)<br /> \]

spełnia zależności $ P(0) = W(a)=0 $ i
$ P(1) = W (a+\varepsilon)= W(b) = 1 $. Nietrudno ponadto spostrzec,
że zbiory wartości wielomianów $ W $ i $ P $ przyjmowanych dla
całkowitych argumentów są równe. Innymi słowy, dla każdego
$ n =0,1,2, \cdots $ istnieje taka liczba całkowita $ k $, że $ P(k)= f_n $.

Niech $ d $ i $ e $ będą takimi liczbami całkowitymi, że
$ P(d)= f_3 = 2 $ oraz $ P(e)= f_4 = 3 $. Wówczas

\[<br /> d-1|P(d)-P (1) = 2-1=1, \text{ skąd } d \in \{0,2\};<br /> \]

wartość $ d = 0 $ wykluczamy, gdyż $ P(0) = 0 \neq 2 $. Zatem $ d = 2 $;
podobnie

\[<br /> e-2|P (e)-P(2) = 3-2=1, \text{ skąd } e \in\{1,3\}<br /> \]

i w efekcie $ e = 3 $. Doszliśmy w ten sposób do wniosku, że

\[<br /> (3) \qquad P(k)= k \text{ dla } k =0,1,2,3.<br /> \]

Wykażemy przez indukcję, że

\[<br /> (4) \qquad P(f_n)= f_n \text{ dla } n =0,1,2, \cdots.<br /> \]

Prawdziwość związku (4) dla $ n \leqslant 4 $ wynika wprost z
relacji (3). Przyjmijmy z kolei, iż równość (4) jest spełniona
dla $ n =0,1, \cdots,m $, gdzie $ m \geqslant 4 $; należy dowieść,
że $ P(f_{m+1})= f_{m+1} $.

Na podstawie założeń zadania istnieje liczba całkowita $ k $,
dla której $ P(k)= f_{m+1} $. Przypuśćmy najpierw, że
$ k < f_{m-1} $; na mocy własności 3. uzasadnionej na początku rozwiązania oraz
nierówności $ m-1 > 2 $ mamy wtedy

\[<br /> f_m - k >f_m - f_{m-1} = f_{m-2} \geqslant \frac{1}{2} f_{m-1},<br /> \]

a ponadto ma miejsce podzielność

\[<br /> f_m -k |P(f_m)-P(k)= f_m-f_{m+1} = -f_{m-1}.<br /> \]

Liczba $ f_m -k $ jest więc dzielnikiem liczby $ f_{m-1} $ większym
od jej połowy, co implikuje równość $ f_m - k = f_{m-1} $. Wówczas
jednak $ k = f_m - f_{m-1} = f_{m-2} $, co nie jest możliwe, gdyż
założenie indukcyjne orzeka, że $ P(f_{m-2})= f_{m-2} $, natomiast
$ P(k)= f_{m+1} $.

Udowodniliśmy tym samym, że $ k \geqslant f_{m-1} $. Ponieważ
na mocy własności 4. oraz warunku $ m \geqslant 4 $ dostajemy

\[<br /> f_{m+1} = f_m +f_{m-1} =2f_{m-1} +f_{m-2} < 3f_{m-1},<br /> \]

więc nierówność $ k \geqslant f_{m-1} $ pociąga za sobą nierównosć
$ k> \frac{1}{3} f_{m+1} $. Z drugiej strony, spełniona jest podzielność

\[<br /> k = k -0|P(k)-P(0) = f_{m+1}-0= f_{m+1}.<br /> \]

W konsekwencji liczba $ k $ jest dzielnikiem liczby $ f_{m+1} $
większym od jej jednej trzeciej. Zatem $ k = f_{m+1} $ lub
$ k = \frac{1}{2} f_{m+1} $. Pierwszy przypadek prowadzi do wniosku,
że $ P(f_{m+1})= f_{m+1} $, co jest tożsame z tezą indukcyjną.
Natomiast drugi przypadek jest niemożliwy: wynikałoby zeń bowiem,
że $ k = 1 $ lub

\[<br /> k-1= \frac{1}{2} f_{m+1}-1|P(k)-P(1) =<br /> f_{m+1}-1 = 2(\frac{1}{2}f_{m+1}-1)+1 = 2(k-1)+1,<br /> \]

a zatem $ k - 1|1 $, czyli $ k \leqslant 2 $. W rezultacie
$ f_{m+1} =2k \leqslant 4 < f_5 $, co przeczy założeniu $ m \geqslant 4 $.

To kończy rozumowanie indukcyjne.

Udowodniona właśnie zależność (4) wraz z własnością 2. pozwala
stwierdzić, że równość $ P(x)= x $ zachodzi dla nieskończenie wielu
liczb całkowitych $ x $. Skoro $ P $ jest wielomianem, równość ta jest
prawdziwa dla każdej liczby rzeczywistej $ x $. Uwzględniając równość
(2) dostajemy teraz

\[<br /> (5)\qquad W(x)= \varepsilon (x-a)<br /> \]

dla każdej liczby rzeczywistej $ x $, gdzie $ \varepsilon \in \{-1,1\} $ oraz $ a $
jest liczbą całkowitą. By zakończyć rozwiązanie, pozostaje już
tylko spostrzec, że każdy wielomian postaci (5) ma żądaną własność.

Komentarze

Dodaj nową odpowiedź