Proving that a closed form is true for $n=k+1$ with induction
$(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
Related videos on Youtube
user133707
Updated on October 14, 2020Comments

user133707 about 3 years
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(n1)+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?

rogerl about 9 yearsYes. If you make that substitution and try to simplify the result into the form you expect, everything should work out.

André Nicolas about 9 yearsYes 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.


user133707 about 9 yearsCan you explain how you went from $(k(k+1)(2k+1))/6 + (k+1)^2$ to the next equation?

CLAUDE about 9 yearsOK. I will add other things after edditing

CLAUDE about 9 yearsDo you understand right now?

user133707 about 9 yearsFantastic, this makes perfect sense. Thank you so much for the help!