You can put this solution on YOUR website! It is easy to prove via induction; but more difficult to derive the formula. To prove it by induction, note that the base case n = 1 holds. Assume it holds for n=k, e.g.
. Then we want to show it works for k+1:
which is what we would've gotten if we substituted k+1 into the formula. Hence the statement is true for all positive integers n.
