I have been asked the following question, and despite spending the last 30 minutes on it, have not come up with a good result:
Define $f(1) = 2$, and $f(n) = f(n-1) + 2n$ for all $n \geq 2$. Find a non-recursive formula for $n$, and prove by induction this formula works over all natural numbers.
So, this didn't sound too hard. I found the non-recursive formula to be $f(n) = n^2 + n$.
Base case of induction with $n = 2$:
$f(2) = 2^2 + 2 = 6$
Assumption step:
$f(k) = k^2 + k$
Extension step:
$\begin{aligned} f(k+1) & = (k+1)^2 + (k+1) \\ & = (k^2 + 2k + 1) + (k+1) \\ & = f(k) + 2k + 2 \ (?) && (\text{Substitute} \ f(k)) \end{aligned}$
Notice it all falls apart here? That extra "$2$" terms means any experimental result I plug in yields a value $2$ higher than it should.
What have I done wrong?