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

You can also do this using a telescoping sum, as we are instructed to use the properties derived in Exercise 2 as much as possible.