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