Задание EGEINFCD7BD4: Рекурсия и рекуррентные зависимости

Дано: аргумент n — целое число. Правила вычисления:
F(n) = n при n ≤ 9.
F(n) = n − 1 + F(n − 1) при n ≥ 10.
Найти R = F(8567) − F(8563).

Используем разность значений, чтобы сократить общий остаток рекурсии. Если F(n) = a(n) + F(n − h), то F(n) − F(n − h) = a(n). Для нескольких шагов:
F(n) − F(n − kh) = a(n) + a(n − h) + … + a(n − (k − 1)h).
Каждое промежуточное значение F входит один раз со знаком плюс и один раз со знаком минус, поэтому сокращается.

Здесь h = 1, число раскрытий k = 4. Раскрываем значения до общего остатка F(8563):
F(8567) = 8567 − 1 + 8566 − 1 + 8565 − 1 + 8564 − 1 + F(8563).
После вычитания F(8563) остаются только добавленные слагаемые:
R = 8567 − 1 + 8566 − 1 + 8565 − 1 + 8564 − 1 = 8566 + 8565 + 8564 + 8563 = 34258.

Все раскрываемые аргументы удовлетворяют условию рекуррентной ветви. До начального значения доходить не нужно: одинаковый остаток сократился точно. Проверка прямым заполнением значений функции от базы даёт F(8567) = 36692434, F(8563) = 36658176. Их разность равна 34258, что подтверждает сокращение.

Ответ: 34258.