Задача
ALG-B3-M06-P019 Шаг три
#19
★★★★★ Уровень 5 из 5
Пусть \(f:\mathbb Z\to\mathbb Z\), \(f(0)=0\), \(f(1)=1\), \(f(2)=4\), и \(f(n+3)-f(n)=6n+9\). Найдите \(f(n)\).
Заметьте, что \((n+3)^2-n^2=6n+9\).
Функция \(n^2\) удовлетворяет рекурсии и трём начальным значениям. Рекурсия с шагом \(3\) отдельно задаёт значения на классах \(0,1,2\pmod3\). Начальные значения на этих трёх классах совпадают с \(n^2\), значит по индукции вперёд и назад \(f(n)=n^2\) для всех целых \(n\).
Проверяет понимание рекурсии по остаточным классам.