Последовательность 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))
 строго возрастает и не ограничена
 никакой константой.
 Тем самым получено противоречие, завершающее доказательство.
			
Периодичность и непериодичность Рекуррентные соотношения (прочее) Доказательство от противного