Now let us assume that it holds for n = k. Then

Using (1), above, we now have
 

Since the formula

is the theorem for n = k + 1, the formula is proved for all integers  with the exception that our proof tacitly assumes that r is neither 0 nor k + 1; that is, it deals only with the coefficients inside the border of 1's. But the formula

shows that each of

Hence the theorem holds in all cases.
 

Monday, June 22, 1998