When , we have
and of course 3 | 6. ("3 divides 6", in case the notation is unfamiliar.)
Suppose this is true for , that
Now for , we have
so we know the left side is at least divisible by by our assumption.
It remains to show that
which is easily done with Fermat's little theorem. It says
where is prime and
is any integer. Then for any positive integer
,
Furthermore,
which goes all the way down to
So, we find that
QED