Solving recursive formulas, proving with induction

Question

I thought I had the answer to this problem but I seem to be off, something is wrong.

The prompt:

Find the exact solution to the following recursive formulas. You may guess the solution and then prove it by induction.

$T(1) = 1$ and $T(n) = T(n-1) + (2n-1)$

Working out the first few in the series:
$T(2) = 4$
$T(3) = 9$
$T(4) = 16$

So I would assume the formula is $T(n) = n^2$

To prove by induction the base case (1) works out, since $1^2 = 1$. Then if I assume $T(n) = n^2$, I try to prove:

$T(n+1) = (n+1)^2$
$T(n) + (2n-1) = (n+1)(n+1)$
$n^2 + 2n-1=n^2+2n+1$

That obviously doesn't add up, so where'd I go wrong?

Answer 1

Since $T(n) =T(n-1)+2n-1 $, replacing $n$ by $n+1$, this becomes $T(n+1) =T(n)+2(n+1)-1 =T(n)+2n+1 $.

This makes your induction work, because $T(n)+2n+1 =n^2+2n+1 =(n+1)^2 =T(n+1) $.

Answer 2

Note that you have $$T(n+1)=T(n)+2(\color{red}{n+1})-1$$ in the inductive step.