Рекуррентная последовательность.

[Imperator]

Пусть $a$ и $b$- два нечетных натуральных числа. Последовательность ${f_{n}}$
определяется следующим образом: $f_{1}=a$, $f_{2}=b,$ а при $n>2$ $f_{n}$
определяется как наибольший нечетный делитель $f_{n-2}+f_{n-1}.$ Докажите,
что для достаточно больших $n$ значение $f_{n}$ постоянно, и найдите это
значение как функцию от $a$ и $b.$

[Руст]

Imperator писал(а):

Пусть $a$ и $b$- два нечетных натуральных числа. Последовательность ${f_{n}}$
определяется следующим образом: $f_{1}=a$, $f_{2}=b,$ а при $n>2$ $f_{n}$
определяется как наибольший нечетный делитель $f_{n-2}+f_{n-1}.$ Докажите,
что для достаточно больших $n$ значение $f_{n}$ постоянно, и найдите это
значение как функцию от $a$ и $b.$

Очевидно, что все члены (являющиеся нечётными числами) не превосходят mаx(a,b) и максимум двух последующих не возрастающая последовательность, поэтому имеет предел , и этот предел является пределом для всей последовательности. Можно оценить и длину стабилизации, которая не превосходит квадрата от max(a,b).

[surfer]

если строить данную последовательность получается что 3й и последующие элементы будут равны наибольшему общему делителю а и б.

[Руст]

Не всегда. Например берите одно из чисел равным 1, а другое $2^k+1.$

[surfer]

невнимательно читал условие

[Руст]

То, что все члены последовательности делятся на НОД(а,в) очевидно. Так как сам процесс выглядит как модифицированный алгоритм нахождения НОД, то и ответом должен быть он.
Пусть $c_n=(f_n,f_{n+1})$. Легко показать, что $c_{n+1}=c_n,c_1=c=gcd(a,b)$. Это доказывает, что последовательность стабилизируется на с.