Suppose for some which was shown.

For the inductive step, you want to show that .

Well .

Since it is known that then .

Also, leads to , so and it follows that . Rearranging, it is evident that .

So applying the above revelations,

It is hypothesized that , so

Thus, , and by induction, is true for all .