Prove that

This implies the sum is proportional to with constant of proportionality 2.

*Proof.*The proof is by induction. For the case we have, on the left,

On the right we have . Hence, the formula holds for this case.

Assume then that the formula holds for some . Then,

Thus, if the statement is true for then it is true for . Hence, we have established the statement is true for all

I don’t understand, why do you begin with the index k=0?, and which is the n+1 termn? (Sorry my english is really bad)

He doesn’t start with the index k=0, it’s just a typo, a mistake.

Then the induction step is where he has to evaluate the sum from k=1 to k=2(m+1), i.e. from k=1 to k=2m +2. We have already assumed the result of the sum from k=1 to k=2m, so he added the last to terms which evaluate the ‘+2’ part. So these two terms are the “n+1” terms you were talking about. There are two because 2(m+1)=2m +(2).