Solve recurrence $T(n) = T(n − 1) + 2n + 1$

inductionrecurrence-relations

Solve recurrence $T(n) = T(n − 1) + 2n + 1$

I have this recurrence to solve. I have found a formula using expanded recursion tree but I am having a hard time applying induction to prove it:
$$f(n) =
\begin{cases}
1, & \text{if $n=1$} \\
T(n − 1) + 2n + 1, & \text{otherwise }
\end{cases}$$

Formula that I want to prove that solves the recurrence $$T(n) = n-1 + n + n^2 -1$$

Base case $$T(1)\quad =\quad n-1 + n + n^2-1 \quad=\quad 0 + 1 + 1 -1 \quad= 1$$

And my failed attempt to prove it works for $n-1$
$T(n-1) = n-2 + n-1 + (n-1)^2 -1 + 2n-1 + 1\\\qquad\quad\;\;\;
= n-2 + n-1 + 2n-1 + (n-1)^2\\\qquad\quad\;\;\;
= n-1 + n-2 + 2n -1 + n^2 – 1$

So I have found $n-1$ and $n^2-1$ from my formula, but I can't seem to get to $n$ and I am stuck on $n-2 + 2n -1$.

I would appreciate any help.

Best Answer

Whenever you see $T(n)-T(n-1)=\cdots$ or equivalently $T(n+1)-T(n)=\cdots$ you should have the reflex to use a telescope.

This is because when summing, all but the first and last terms will cancel out, this is called a telescoping sum.

$\begin{array}{lcll}\require{cancel} T(n)&-&\cancel{T(n-1)}&=a_n\\ \cancel{T(n-1)}&-&\cancel{T(n-2)}&=a_{n-1}\\ \cdots&&&\cdots\\ \cancel{T(2)}&-&T(1)&=a_2\\\hline T(n)&-&T(1)&=\sum\limits_{i=2}^n a_i \end{array}$

In our case this would result in:

$\displaystyle\begin{align} T(n)&=T(1)+\sum\limits_{i=2}^n (2i+1)\\&=1+2\sum\limits_{i=2}^n i+\sum\limits_{i=2}^n1\\&=1+2\left(\frac{n(n+1)}2-1\right)+(n-1)\\&=n^2+2n-2\end{align}$

You could object that you still need to prove $\sum i=\frac{n(n+1)}2$ by induction, well that's fair, though you can prove it by summing two times in reverse order $(1+2+\cdots+n)+(n+\cdots+2+1)$.

Anyway let's go back to your method and try to prove it directly by induction:

Let assume: $\,T(n)=n^2+2n-2$

$T(1)=1+2-2=1\quad\checkmark$

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

Now remember that we want $(n+1)^2+2(n+1)-2=n^2+2n+1+2n+2-2=n^2+4n+1$, and this is the same $\quad\checkmark$

Therefore the induction is verified.

Regarding your mistakes:

  • use the simplified formula $n^2+2n-2$ instead of the fully developed one $n-1+n-n^2-1$ it is easier to handle less terms.
  • in the induction you went backward, you either assume $T(n-1)$ and prove $T(n)$ or assume $T(n)$ and prove $T(n+1)$ not the opposite.
  • use parenthesis, $n-1^2$ is not $(n-1)^2$ and $2n-1$ is not $2(n-1)$, this is prone to error to omit them.

Finally you can do like I did, calculate the simplified expression for $T(n+1)$ in both cases (what the end result should be, and what is it when carrying induction hypothesis) and check they are both the same. This direct calculation is easier than trying to reverse engineering it to $(n+1)^2$ and similar terms.

Related Question