Prove that is true for all positive integers .

Let be the statement that .

Verify that is true for .

is true for .

Assume that is true for .

Substitute in .

.

is true for positive integer .

Show that must be true.

Consider .

Add next term on each side.

\ \

.

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,

  or is true for all positive integers .

By the principle of mathematical induction, or is true for all positive integers .