Для начала заметим, что носители размножаются независимо друг от друга. А значит, достаточно почитать ответ ans, если изначально был только один носитель, тогда итоговое количество — ans × n. Все дальнейшее рассуждение предполагает, что изначально есть только один носитель.
Пусть Ai — количество носителей, появившихся за i-ый дней. То есть
A1 = 2, A2 = 5, A3 = 13 и так далее.
Тогда верно равенство
An = An - 1 + , где An - 1 — количество носителей, появившихся за n - 1 день,
— количество новых носителей.
Заметим, что F2k = Ak. Докажем данное утверждение по индукции.
Предположим, что для 1 lei lek равенство верно. Тогда докажем равенство для k + 1. То есть мы хотим доказать, что
F2(k + 1) = Ak + 1, тогда
Ak + 1 = Ak + = F2k + F2k - 1
Заметим, что Ak = F2k по индукционному предположению. Тогда должно соблюдаться, что
= F2k - 1
Вновь распишем левую и правую части равенства, получим
= Ak - 1 +
= F2k - 2 + F2k - 3
Вновь заметим, что по индукционному предположению
Ak - 1 = F2k - 2. Тогда повторим процесс заново для оставшейся суммы, каждый раз индексы будут уменьшаться, и одно из слагаемых и в правой и в левой части будут сокращаться. В итоге придем к равенству
A1 = F2 — очевидно верно.