-
Let .
When ,
, and
when ,
.
We have also
Therefore, we have
as desired.
-
Using the same substitution, we have
Therefore,
|
is equivalent to
|
is equivalent to
|
is equivalent to
|
Notice that
This means
|
which is exactly what was desired.
-
Proof by induction:
-
Base Case. When ,
|
-
Induction Hypothesis. Assume for some
,
we have
|
-
Induction Step. When ,
Therefore, by the principle of mathematical induction, for
,
|
as desired.