Sunday, October 28, 2018

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





usually the tasks look like



ni=0i2=(n2+n)(2n+1)6



or




ni=0i2=i21+i22+i23+...+i2n



But for the following task I have this form:



(nk=1k)2=nk=1k3



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 (nk=1k)2=nk=1k3 holds for n. We want to show that (n+1k=1k)2=n+1k=1k3. How to do it? Note that



(n+1k=1k)2=(nk=1k+n+1)2=(nk=1k)2+2(n+1)nk=1k+(n+1)2=inductionhypothesisnk=1k3+2(n+1)nk=1k+(n+1)2=n+1k=1k3 if and only if (n+1)3=2(n+1)nk=1k+(n+1)2. Show this equality and you are done.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...