Задачник Арнольда (числа Фибоначчи)

[dserp18]

Задача №43. Найти НОД чисел Фибоначчи $a_{100}$ и $a_{99}$.
Наверное, надо по алгоритму Евклида раскладывать числа, т.е.
$\frac{ 21 }{ 13 } =13\times1+8$,
$13=8+5$,
$8=5+3$,
$5=3+2$,
$3=2+1$,
$2=1+1$.
Т.о. НОД =1 (для соседних чисел)?

[grizzly]

dserp18 в сообщении #1327346 писал(а):

Т.о. НОД =1 (для соседних чисел)?

Да.

[iifat]

dserp18 в сообщении #1327346 писал(а):

Т.о. НОД =1 (для соседних чисел)?

Что значит — для соседних? Если вопрос про доказательство, то доказали вы пока что $\text{НОД}(21,13)=1$. Хотя да, общее доказательство вполне можно увидеть.

[Shadow]

Странная задача....если соседние числа Фибоначчи имеют общий делитель, то все числа Фибоначчи будут иметь этот делитель (рекуррентная формула)

[dserp18]

iifat в сообщении #1327350 писал(а):

Хотя да, общее доказательство вполне можно увидеть.

Наверное, по индукции можно утверждать, что НОД $ =1 $ для $a_{n}$ и $a_{n+1} $.
Но как это доказать?

Сначала (для доказательства по индукции) надо проверить гипотезу при $n=1$. Так?

[eugensk]

Shadow
Нет, несоседние необязательно, возьмите 8 и 2, например. Из рекуррентной формулы следует только, что $\text{НОД}(a_{n+2},a_{n+1}) = \text{НОД}(a_{n+1}, a_n)$.
Если докажете это, то сможете применить индукцию.
Grizzly
Да, мне не стоило читать форум между делом. Конечно, заключение Shadow в том, что все делятся на 1 (как первые два), и мой пример - не пример.

[grizzly]

eugensk в сообщении #1327392 писал(а):

Нет, несоседние необязательно, возьмите 8 и 2, например.

Посмотрите внимательнее на посылку и следствие в сообщении Shadow. Что бы Вы не имели в виду, но это не пример.

[dserp18]

grizzly в сообщении #1327393 писал(а):

eugensk в сообщении #1327392 писал(а):

Нет, несоседние необязательно, возьмите 8 и 2, например.

Посмотрите внимательнее на посылку и следствие в сообщении Shadow. Что бы Вы не имели в виду, но это не пример.

Обычно говорят о наибольшем общем делителе ДВУХ целых чисел

-- 18.07.2018, 12:56 --

eugensk в сообщении #1327392 писал(а):

Из рекуррентной формулы следует только, что $\text{НОД}(a_{n+2},a_{n+1}) = \text{НОД}(a_{n+1}, a_n)$.
Если докажете это, то сможете применить индукцию.

Наверное $\text{НОД}(a_{n+2},a_{n+1}) = \text{НОД}(a_{n+1}, a_n)$ можно доказать по индукции?

[eugensk]

dserp18 в сообщении #1327394 писал(а):

Обычно говорят о наибольшем общем делителе ДВУХ целых чисел

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

dserp18 в сообщении #1327394 писал(а):

Наверное $\text{НОД}(a_{n+2},a_{n+1}) = \text{НОД}(a_{n+1}, a_n)$ можно доказать по индукции?

Нет. Используйте рекуррентную формулу. Докажите, что при произвольном n общие делители $a_{n+2}$ и $a_{n+1}$ будут те же, что и общие делители $a_{n+1}$ и $a_{n}$. Тогда и наибольшие делители будут одни и те же.

[iifat]

dserp18 в сообщении #1327377 писал(а):

Так?

Ну дык приступайте же ж! Так и будете спрашивать, «Теперь надо сложить 1+1. Так? Получим 2. Так?» Вам уже, почитай, всё доказательство расписали, а вы ещё и до $\text{НОД}(1,1)$ не дошли.

[ewert]

Shadow в сообщении #1327355 писал(а):

Странная задача....если соседние числа Фибоначчи имеют общий делитель, то все числа Фибоначчи будут иметь этот делитель (рекуррентная формула)

Здесь имелась в виду индукция не столько вверх, сколько вниз. Если предположить, что какое-то число для двух соседних членов является общим делителем, то оно же будет таковым и у предыдущей пары соседних.

[eugensk]

(wishes/lamentations)

Я зарекаюсь влазить как следует не прочитав, теперь и мне понятно, что имелось ввиду :) Лишь бы ТС всё решил, дай бог ему просветления.

[dserp18]

Спасибо.
"В общем виде рекуррентное соотношение $u_{n+2}=u_{n+1}+u_{n}$
можно записать как
$ x_{n+k} = a_{1}x_{n+k-1}+a_{2}x_{n+k-2}+...+a_{k}x_{n}$
Число $k$ называют порядком соотношения.
Соотношение Фибоначчи имеет второй порядок."

А почему $k=2$ для чисел Фибоначчи?

[grizzly]

dserp18 в сообщении #1327424 писал(а):

А почему $k=2$ для чисел Фибоначчи?

Странный вопрос, но попытаюсь ответить.
Наоборот. При $k=2$ (а также при $a_1=a_2=1$) числа получившейся последовательности называют числами Фибоначчи.

[dserp18]

Спасибо (невнимательно прочитал учебник). Вопрос: а для чисел Люка характеристическое уравнение будет таким
$\lambda^2=2\lambda+1 $