Let be the statement that is divisible by .

is the staement that is divisible by .

is true.

Assume is true, where is positive integer.

Prove that must be true.

for some integer as is true.

Since is positive integer, is an integer.

Thus, is divisible by .

The final statement is exactly , so is true.

Because is true for and implies , is true for and so on.

That is, by the principle of mathematical induction is divisible by for all positive integers .

is divisible by for all positive integers .