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

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

Используем разность значений, чтобы сократить общий остаток рекурсии. Если 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 = 9, число раскрытий k = 3. Раскрываем значения до общего остатка F(5074):
F(5101) = 5101² + 5092² + 5083² + F(5074).
После вычитания F(5074) остаются только добавленные слагаемые:
R = 5101² + 5092² + 5083² = 26020201 + 25928464 + 25836889 = 77785554.

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

Ответ: 77785554.