Question

Докажите, что среди чисел Фибоначчи есть сколько угодно чисел, оканчивающихся на 013​

Answer 1

$F_0=0,F_1=1, F_n=F_{n-1}+F_{n-2}, n\in N\backslash\{1\}$

Заметим, что $F_7=13$

Докажем, что, начиная с $F_7$, последовательность Фибоначчи периодическая по модулю 1000.

Рассмотрим $1000^2+1$ пару чисел $(F_7,F_8),(F_8,F_9),...,(F_{1000^2+7},F_{1000^2+8})$ .

Каждое из чисел каждой из пар дает один из $1000$ остатков по модулю $1000$ . Тогда всего вариантов пар остатков от деления на 1000 может быть $1000*1000=1000^2$ (1000 вариантов остатков 1ого числа пары и 1000 вариантов у 2ого).

Тогда, по принципу Дирихле, в рассматриваемом мн-ве пар найдутся хотя бы 2 пары чисел, соответствующие элементы которых сравнимы по модулю 1000 - а, с учетом определения последовательности Фибоначчи, это и означает периодичность остатков ее членов по модулю 1000.

Возьмем 2 такие пары с наименьшими номерами. Пусть это пары $(F_i,F_{i+1}), (F_j,F_{j+1}), i$. Покажем, что $i=7$.

Пусть не так, и $i>7$.

По построению, $F_i\equiv F_j(mod \;1000),F_{i+1}\equiv F_{j+1}(mod \;1000)\Rightarrow F_{i+1}-F_{i}\equiv F_{j+1}-F_{j}(mod \;1000)$

Но, по определению последовательности Фибоначчи, $F_{k+1}-F_{k}=F_{k-1},k\in N$ . А значит $F_{i-1}\equiv F_{j-1}(mod\; 1000)$. А тогда соответствующие элементы пар чисел $(F_{i-1},F_i),(F_{j-1},F_j)$ сравнимы по модулю 1000 - противоречие с тем, что $(F_i,F_{i+1}), (F_j,F_{j+1}), i$ - пары с наименьшими номерами.

Значит $i=7$.

А это означает, что в последовательности остатков от деления членов последовательности Фибоначчи на 1000 найдется сколь угодно чисел, сравнимых с $F_7$ по модулю 1000. Т.к последовательность возрастающая и неограниченная, начиная со 2ого члена, это утверждение эквивалентно условию задачи.

Доказано.

________________________________

Можно доказать аналогичным образом и более общее утверждение: последовательность чисел Фибоначчи по модулю $q\in N$ периодическая (вышеприведенные рассуждения - частный случай этого док-ва). Длина периода такой последовательности обозначается $\pi(q)$ и называется период Пизано.

Answer 2

Давайте докажем это утверждение индукцией.

Пусть у нас есть два числа Фибоначчи, оканчивающихся на 013. Давайте обозначим их как F_n и F_m, где n > m. То есть числа Фибоначчи F_n и F_m имеют вид:

F_n = k₁ * 10ⁿ + 13 F_m = k₂ * 10^m + 13

где k₁ и k₂ - какие-то целые числа.

Рассмотрим число F_n+2:

F_n+2 = F_n+1 + F_n

Следовательно:

F_n+2 = (k₁ * 10ⁿ⁺¹ + 13) + (k₁ * 10ⁿ + 13) F_n+2 = k₁ * 10ⁿ * (10 + 1) + 26

Таким образом, число F_n+2 также оканчивается на 013.

Итак, если у нас есть два числа Фибоначчи, оканчивающихся на 013, то мы можем построить следующее число Фибоначчи, которое также оканчивается на 013.

По индукции можно утверждать, что среди чисел Фибоначчи найдется сколько угодно чисел, оканчивающихся на 013.