Знания — сила

Для начала заметим, что носители размножаются независимо друг от друга. А значит, достаточно почитать ответ 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 — очевидно верно.