Look at the code and write out the variables.

Find some pattern and the result

Base Case: Prove p(n0) where n0 is usually 1. Make n=0, first.

Assume it holds true for P(k) for k>n0. (What happens for n1, n2, n3?)

Prove Inductive Case (if P(K) is true, then P(k+1) is true.