16. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n)=n,при n>100000 F(n)=F(n+1)+5n+2,при остальных n Чему равно F(3) – F(7

Задача задаёт рекурсивную функцию F(n): - F(n) = n, если n > 100000 - F(n) = F(n+1) + 5n + 2, если n ≤ 100000 Нужно найти F(3) − F(7). 1) Общий подход по шагам - Для любых n ≤ 100000 можно «развернуть» рекурсию k раз: F(n) = F(n+k) + sum_{i=0}^{k−1} [5(n+i) + 2]. - Берём k так, чтобы n+k стало больше 100000. Выбираем k = 100001 − n. тогда n+k = 100001, и F(100001) = 100001 (база). - Подстановкой получаем: F(n) = 100001 + k(5n+2) + (5/2) k(k−1), где k = 100001 − n. 2) Вычисления для F(3) - n = 3 → k = 100001 − 3 = 99998. - 5n + 2 = 5·3 + 2 = 17. -_term1_ = k(5n+2) = 99998 · 17 = 1 699 966. - k(k−1) = 99998 · 99997 = 9 999 500 006. - _term2_ = (5/2) k(k−1) = (5 · 9 999 500 006) / 2 = 24 998 750 015. - F(3) = 100001 + 1 699 966 + 24 998 750 015 = 25 000 549 982. 3) Вычисления для F(7) - n = 7 → k = 100001 − 7 = 99994. - 5n + 2 = 5·7 + 2 = 37. - _term1_ = k(5n+2) = 99994 · 37 = 3 699 778. - k(k−1) = 99994 · 99993 = 9 998 700 042. - _term2_ = (5/2) k(k−1) = (5 · 9 998 700 042) / 2 = 24 996 750 105. - F(7) = 100001 + 3 699 778 + 24 996 750 105 = 25 000 549 884. 4) Разность F(3) − F(7) = 25 000 549 982 − 25 000 549 884 = 98. Ответ: 98.