Claim:
Proof. For , on the left we have 1 and on the right we have
. Thus, the formula holds for the case
.
Assume then that the formula is true for some . Then,
Hence, if the statement is true for , then it is true for
. Since we have established that it is true for
, we then have that it is true for all