Условие
Последовательность f(n) (n=1,2,...), состоящая из натуральных
чисел, такова, что f(f(n))=f(n+1)+f(n) для всех натуральных n.
Докажите, что все члены этой последовательности различны.
Подсказка
Предположите противное и выведите из этого предположения, что
последовательность периодическая начиная с некоторого члена.
Решение
Предположим противное: для некоторых различных натуральных k и m
выполнено
f(k)=f(m). Тогда f(f(k))=f(k+1)+f(k) и f(f(m))=f(m+1)+f(m),
откуда f(k+1)=f(f(k))-f(k) и f(m+1)=f(f(m))-f(m).
Правые части полученных равенств по нашему предположению равны,
следовательно, f(k+1)=f(m+1).
Рассуждая далее таким же образом, получаем, что
f(k+2)=f(m+2), f(k+3)=f(m+3), и т.д.
Таким образом, для любого натурального n,
большего k и m, выполнено f(n)=f(n+|m-k|).
Итак, начиная с некоторого члена последовательность периодична с
периодом |m-k|.
Это, в частности, означает, что все члены последовательности
ограничены некоторой константой.
С другой стороны f(f(n))=f(n+1)+f(n)>f(n), поскольку f(n+1) -
натуральное.
Следовательно, последовательность f(n),
f(f(n)),...,f(f...(f(n))...)
(являющаяся подпоследовательностью последовательности f(n))
строго возрастает и не ограничена
никакой константой.
Тем самым получено противоречие, завершающее доказательство.
Источники и прецеденты использования
