# Proving that a closed form is true for $n=k+1$ with induction

2,448

$(1)-$ For $n=1$ it is apparent.

$(2)-$ Suppose that the assumption holds for $n=k$, and it means: $T(k)=\frac{k(k+1)(2k+1)}{6}$

$(3)-$ We wanna prove the assumption for $n=k+1$

$T(k+1)=T(k)+(k+1)^2=\frac{k(k+1)(2k+1)}{6}+(k+1)^2=\frac{k(k+1)(2k+1)+6(k+1)^2}{6}=\frac{k(k+1)(2k+1)+6(k+1)(k+1)}{6}=\frac{(k+1)(2k^2+k)+(k+1)(6k+6)}{6}=\frac{(k+1)(2k^2+7k+6)}{6}=\frac{(k+1)(2k^2+4k+3k+6)}{6}=\frac{(k+1)(2k(k+2)+3(k+2))}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$

So the assumption is true

Share:
2,448

Author by

### user133707

Updated on October 14, 2020

I need to prove that a closed form formula is true for n=k+1. I need to use mathematical induction and explain every step, but I'm getting lost on this one. I already found the closed form, and I made a table comparing recursive and closed form outputs, so I know it's correct.

The recurrence is $T(n)=T(n-1)+n^2$ with $T(1)=1$.

The closed form is $T(n)=(1/6)*n(n+1)(2n+1)$

I would assume it should be started off with something like this:

(1). $T(k+1)=T((k+1)-1)+(k+1)^2$ -This is from the definition of the recurrence with $n=k+1$

(2). $T(k+1)=T(k)+(k+1)^2$ -Note that $(k+1)-1=k$

Now I start to get confused. Is this where I can bring in induction and replace $T(k)$ with my closed form that I already have?

Yes you can. Then manipulate the expression you get until you arrive at $\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$. It should not be hard, bring to a common denominator $6$, note the common factor $k+1$ on top.
Can you explain how you went from $(k(k+1)(2k+1))/6 + (k+1)^2$ to the next equation?