e-olymp 2060. Сказка о яблоке.

Задача взята с сайта e-olymp

Задача

Однажды царь наградил крестьянина яблоком из своего сада. Пошёл крестьянин к саду и видит: весь сад огорожен $n$ заборами, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошёл крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несёшь, и ещё одно». То же ему сказали и второй, и третий сторож и т.д. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

Входные данные

Количество заборов $n; \; (1 \leqslant n \leqslant 62)$ в саду.

Выходные данные

Вывести количество яблок, которое должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 4
2 3 22
3 30 50331646
4 60 3458764513820540926
5 62 13835058055282163710

Код.Циклы

Код.Линейное решение

Решение

Последовательность необходимых количеств яблок задается формулой $x_{n+1}=2 \cdot (x_{n}+1); \; x_{1}=1.$ Мы можем поочередно вычислять элементы последовательности через цикл, или воспользоваться линейной формулой  $x_{n}=(3\cdot 2^n)-2.$

Выведение линейной формулы:

Преобразуем исходное выражение: $x_{n+1}=2 \cdot x_{n}+2$. Можно видеть, что каждая следующая итерация увеличивает степень всех двоек входящих в предыдущую на 1 и добавляет 2. Выпишем формулу для номера $n+m:$ $x_{n+m}=2^{m}x_ n+2_x^{m-1}+…+2$. Можно увидеть, что  $x_{n+m}$ содержит в себе слагаемое $2^{m}x$ , а так же сумму слагаемых вида  $\displaystyle \sum_{i=1}^{m}2^i$. Если учесть, что $\displaystyle x_{1}=1$, то  $\displaystyle x_n=2^{n}+  \sum_{i=1}^{n}2^i=2^{n+1}+2^n -2 = 2^{n}\cdot(1+2)-2= 3\cdot 2^n-2.$ Следовательно формула $n$-го члена — $x_n= 3\cdot 2^n-2$.

Решения на ideone