Последовательность

[wpoms.]

Докажите, что последовательность, определенная условиями `y_0 = 1`, `y_{n+1} = 1/2(3y_n + sqrt(5y_n^2 - 4))`, (`n >= 0`), состоит только из целых чисел.

@темы: Теория чисел

Comments

[Trotil]

Выводим несколько членов последовательности вручную. Ими оказываются нечётные члены Фибоначчи.
Раз так, делаем финт: берём эту формулу: upload.wikimedia.org/math/3/b/0/3b02a70614ef9ca... и подставляем в реккурентную формулу, упрощаем.
Вуаля.

[Adjirranirr]

Рассмотрим функцию `f:\ RR^+ -> RR^+:\ f(x) = 1/2 (3 * x + \sqrt(5*x^2 - 4))`.
Тогда `f(f(x)) + x = 1/2 (3 f(x) + \sqrt(5 f(x)^2 - 4)) + x =9/4 x + 3/4 \sqrt(5x^2 - 4) + 1/2 \sqrt (5 * (3/2 x + 1/2 \sqrt(5x^2 - 4))^2 - 4) + x =`
`= 1/2 (13/2 x + 3/2 \sqrt(5x^2 - 4) + \sqrt(35/2 x^2 + 15/2 x * \sqrt(5x^2 - 4) - 9))`
Будем искать `35/2 x^2 + 15/2 x * \sqrt(5x^2 - 4) - 9` в виде `(a x + b \sqrt(5x^2 - 4))^2`; тогда
`35/2 x^2 + 15/2 x * \sqrt(5x^2 - 4) - 9 = (a^2 + 5b^2) x^2 + (2ab) x * \sqrt(5x^2 - 4) - 4 b^2`
`b = 3/2,\ a = 5/2`.
Таким образом,
`f(f(x)) + x = 1/2 (13/2 x + 3/2 \sqrt(5x^2 - 4) + 5/2 x + 3/2 \sqrt(5x^2 - 4)) = 1/2 (9 x + 3 \sqrt(5x^2 - 4)) = 3 f(x)`
`f(f(x)) = 3 f(x) - x`.
А так как `y_0 = 1,\ y_1 = f(1) = 2`, то из `f(f(y_n)) = 3 f(y_n) - y_n <=> y_(n + 2) = 3 y_(n + 1) - y_n` следует, что `y_n \in ZZ \ AA n\in NN`.