Let be the statement that .

In the fibonacci sequence each element after the first two is found by adding the previous two terms.

represents the fibonacci number.

and .

Here .

.

Therefore, is true for an positive integer .

As is true,then must also be true.

The final statement is excatly , Therefore is true.

Because is true for and implies .

is true for and so on.

Therefore, is true for all positive integers of .

is proved.