Saturday, December 3, 2016

summation - Proof by induction: showing that two sums are equal




usually the tasks look like



$$\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6}$$



or



$$\sum_{i=0}^n i^2 = i_1^2 + i_2^2 + i_3^2+...+i_n^2$$




But for the following task I have this form:



$$\left(\sum_{k=1}^n k\right)^2 = \sum_{k=1}^nk^3 $$



First I am a little confused by how I approach this. Do I transform them into a complete term like in the first example? Or can I do it by just using the sums themselves? And how should I treat the square of the sum best?



The first step is pretty straight forward creating the base case. But as soon as I get into doing the "Induction Step" I am getting stuck and not sure how to proceed.



I am looking to know best practice for this case.




Edit:
This question is a little different, since it is expected to proove this only by using complete induction using the sum notation.


Answer



Assume that $\displaystyle\left(\sum_{k=1}^n k\right)^2 = \sum_{k=1}^nk^3$ holds for $n.$ We want to show that $\displaystyle\left(\sum_{k=1}^{n+1} k\right)^2 = \sum_{k=1}^{n+1}k^3.$ How to do it? Note that



$$\begin{align}\left(\sum_{k=1}^{n+1} k\right)^2&=\left(\sum_{k=1}^{n} k+n+1\right)^2\\&= \color{blue}{\left(\sum_{k=1}^{n} k\right)^2}+2(n+1)\sum_{k=1}^nk+(n+1)^2\\&\underbrace{=}_{\rm{induction}\:\rm{hypothesis}}\color{blue}{\sum_{k=1}^nk^3}+\color{red}{2(n+1)\sum_{k=1}^nk+(n+1)^2}\\&=\sum_{k=1}^{n+1}k^3\end{align}$$ if and only if $\displaystyle(n+1)^3=2(n+1)\sum_{k=1}^nk+(n+1)^2.$ Show this equality and you are done.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...