To prove for all positive integers all you have to do is show

(i) that , and

(ii) that if for some then also for that very same .

Here we go.

Let .

Initial step: , so .

Inductive step: Assume that for some .

Then .

Thus, by the principle of induction, for all positive integers .