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).