Задача про числа Фибоначчи

[Nilenbert]

Доказать, что существует бесконечно много чисел Фибоначчи, делящихся на свой номер, т.е. $n|F_n$. (Считаем, что $F_0=0$, $F_1=1$)

(Оффтоп)

Собственно, когда-то я обнаружил, для всех членов некоторой последовательности это свойство верно. Через некоторое время нашлась и вторая последовательность. А потом я решил глянуть на OEIS, и там нашлось гораздо более простое доказательство.

Задачка эта самоочевидная, и поэтому я боюсь что она уже бывала тут, но поиск не дал похожих вещей.

[TOTAL]

$F_{2m}=F_{m}(F_{m-1}+F_{m+1})$
$F_{12}=144$ делится на $12$, поэтому $F_{24}$ делится на $24$ и т.д

[Sonic86]

Можно доказать, что $5^k|F_{5^k}$ по индукции из формулы $F_{5n}=25F_{n}^5+25(-1)^{n}F_n^3+5F_{n}$, которая, скорее всего, выводится из тождества $F_{n+m}=F_{n-1}F_{m}+F_{n}F_{m+1}$. А вообще множество таких чисел $n$ выглядит плотнее:
$1,5,12,24,25,36,48,60,72,96,108,120,125,144,168,180,192,216,240,288,300,324,336,360,384,$ $432,480,504,552,576,600,612,625,648,660,672,684,720,768,840,864,900,960,972$

[Nilenbert]

ОК, замечательно. Собственно как у меня было:
Сначала я игрался с формулой Бинэ и получил формулу: $F_{5n}=5F_n(F_{2n}^2+(-1)^n F_n^2+1)$ и далее как у Sonic86.

Через некоторое время набрёл на решение как у TOTAL.

Вот, но осталось ещё третье решение.

[Sonic86]

Еще, видимо, так: если $n|F_n$, то $(\forall k)n^k|F_{n^k}$. Только доказать затрудняюсь.

[maxal]

См. также комментарии в A023172.

-- Mon Oct 24, 2011 06:31:19 --

Sonic86 в сообщении #491827 писал(а):

Еще, видимо, так: если $n|F_n$, то $(\forall k)n^k|F_{n^k}$. Только доказать затрудняюсь.

Более общее утверждение, которое довольно просто доказать: если $n|F_n$, то $(pn)|F_{pn}$ для всякого простого $p|n$.