for some .

First we see if it holds for

, therefore true for

Now we use what's called the induction step, we assume that it's true for where k is some natural nubmer.

This gives us

We then prove this for , giving us

.

Expanding the brackets gives

which can be written as

.

Therefore it is true for if true for .

You know it is true for 0, therefore true for 1. True for one, therefore true for 2....

Hope this helps