Monday, 21 April 2014

summation - Prove that for ninmathbbN,sumlimitsnk=1(2k+1)=n2+2n



I'm learning the basics of proof by induction and wanted to see if I took the right steps with the following proof:




Theorem: for nN,nk=1(2k+1)=n2+2n



Base Case:



let n=1

Therefore 21+1=12+21
Which proves base case is true.



Inductive Hypothesis:



Assume nk=1(2k+1)=n2+2n




Then n+1k=1(2k+1)=(n+1)2+2(n+1)


(2(n+1)+1)+nk=1(2k+1)=(n+1)2+2(n+1)

Using inductive hypothesis on summation term:
(2(n+1)+1)+n2+2n=(n+1)2+2(n+1)

2(n+1)=2(n+1)



Hence for nN,nk=1(2k+1)=n2+2n Q.E.D.



Does this prove the theorem? Or was my use of the inductive hypothesis circular logic?



Answer



Your proof looks fine, but if you know that
1+2+...+n=n(n+1)2


then you can evaluate
nk=1(2k+1)=2nk=1k+nk=11=/2n(n+1)/2+n=n2+2n


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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