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

Related videos on Youtube

user133707
Author by

user133707

Updated on October 14, 2020

Comments

  • user133707
    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(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?

    • rogerl
      rogerl about 9 years
      Yes. If you make that substitution and try to simplify the result into the form you expect, everything should work out.
    • André Nicolas
      André Nicolas about 9 years
      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.
  • user133707
    user133707 about 9 years
    Can you explain how you went from $(k(k+1)(2k+1))/6 + (k+1)^2$ to the next equation?
  • CLAUDE
    CLAUDE about 9 years
    OK. I will add other things after edditing
  • CLAUDE
    CLAUDE about 9 years
    Do you understand right now?
  • user133707
    user133707 about 9 years
    Fantastic, this makes perfect sense. Thank you so much for the help!