Problem
ALG-B3-M01-P003 Recursion as a function
#3
★★☆☆☆ Level 2 of 5
Let \(f:\mathbb N^{*}\to\mathbb Z\), where \(\mathbb N^{*}=\{0,1,2,\ldots\}\), \(f(0)=1\), \(f(n+1)=f(n)+2n+3\). Find \(f(n)\).
Hint. Sum the increments from \(0\) to \(n-1\).
We have \(f(n)=1+\sum_{k=0}^{n-1}(2k+3)=1+n(n-1)+3n=(n+1)^2\). The recurrence check is immediate.
Goal: separate guessing the answer from a complete proof and domain check.