Задача про последовательность

Условие:

Есть последовательность заданная x(1)=1 и следующей рекуррентной формулой:

Рекуррентная формула

Напомню что рекуррентная формула- это формула по которой из известных членов последовательности можно посчитать следующий.

Найдите x(2017).

Решение:

Исследовав функции y(n)=x(n)-n и x(n) находим явный вид последовательности:

Найдем максимальную степень двойки k, что она меньше n, тогда:

Явный вид

Докажем что это явный вид.

Для начала проверим n=1

x(1)=1

Теперь проверим что выполняется рекуррентная формула

Доказательство рекуррентной формулы

Следовательно мы узнали явный вид, значит посчитать какой-нибудь член последовательности не проблема.

Подсчет ответа

Ответ: x(2017)=24225