Задание №16 — Рекурсия

Решение:

Выражение сворачивается, если аккуратно раскрыть значения по рекуррентному правилу $F(n) = n(n-1) + F(n-1) + F(n-2)$.

При $n = 2023$: $F(2023) = 2023 \cdot 2022 + F(2022) + F(2021)$, поэтому $F(2023) - F(2021) = 2023 \cdot 2022 + F(2022)$.

При $n = 2022$: $F(2022) = 2022 \cdot 2021 + F(2021) + F(2020)$, а при $n = 2021$: $F(2021) = 2021 \cdot 2020 + F(2020) + F(2019)$. Подставив второе в первое, получаем $F(2022) = 2022 \cdot 2021 + 2021 \cdot 2020 + 2F(2020) + F(2019)$.

Тогда все неизвестные значения сокращаются:

$$F(2023) - F(2021) - 2F(2020) - F(2019) = 2023 \cdot 2022 + 2022 \cdot 2021 + 2021 \cdot 2020 = 4090506 + 4086462 + 4082420 = 12259388.$$

Проверка программой (значения растут очень быстро, но в Python целые числа длинные, поэтому переполнения не будет):

F = [0] * 2024
F[1], F[2] = 1, 2
for n in range(3, 2024):
    F[n] = n * (n - 1) + F[n - 1] + F[n - 2]

print(F[2023] - F[2021] - 2 * F[2020] - F[2019])   # 12259388

Ответ: 12259388