Monday, 21 August 2017

Prove summation using induction




$$\sum\limits_{i=1}^n i^3 = \left(\frac{n(n + 1)}{2}\right)^2$$




My basis step is $P(1)$ sets the $LHS = RHS = 1$.



For the inductive step, I assume $n = k$ holds for $k+1$. On the $RHS$:



$$\left(\frac{(k + 1)((k + 1) + 1)}{2}\right)^2$$



But I don't know how to convert the summation into something that can evaluated algebraically.



Disclaimer: this is a question from an exam review sheet.


Answer




I assume that $P(n)$ means that the formula holds for $n$.



You assume that this holds for $n=k$ and you want to show that this holds for $n = k+1$.
On the right hand side you indeed have what you have written.



One the left hand side you have
$$
\sum_{i=1}^{k+1} i^3 = \left[\sum_{i=1}^{k} i^3\right] + (k+1)^3
$$
Now you can use the induction hypothesis and continue to get

$$
\left[\sum_{i=1}^{k} i^3\right] + (k+1)^3 = \left(\frac{k(n+1)}{2}\right)^2 + (k+1)^3.
$$
All that is left for you to show is that
$$
\left(\frac{k(n+1)}{2}\right)^2 + (k+1)^3
$$
is equal to the right hand side that you have in your question.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...