Prove:

*Proof.*We prove by induction. If , then the statement is true since . Assume then that the statement is true for some . So,

Where the final step follows since the value of 1 for is still 1. (Maybe this could confuse since we are summing over the index , but the value is independent of . So, really, we are just counting… so for each in the index we add 1; thus, when we have the sum from to and add 1, it is the same as summing from to ). Thus, by induction, the statement is true for all