Problem
ALG-B3-M06-P019 Step Three
#19
★★★★★ Level 5 of 5
Let \(f:\mathbb Z\to\mathbb Z\), \(f(0)=0\), \(f(1)=1\), \(f(2)=4\), and \(f(n+3)-f(n)=6n+9\). Find \(f(n)\).
Notice that \((n+3)^2-n^2=6n+9\).
The function \(n^2\) satisfies the recurrence and the three initial values. A step-three recurrence determines values separately on the classes \(0,1,2\pmod3\). The initial values on these three classes agree with \(n^2\), so by induction forward and backward \(f(n)=n^2\) for all integers \(n\).
Checks understanding of recurrences by residue classes.