The base case is trivial (everything is proportional to 1), so let n = 2. Then

So assume that the theorem is true for some n = N. Then we need to show that it is true for n = N + 1. Let the constant of proportionality be 2, since this is true of the n = 2 case.

This is proportional to N + 1 with a constant of proportionality 2. So etc, etc.

-Dan