First we prove the Lemma:
Proof of Lemma:
, using the fact that and
Then the Induction Hypothesis: Suppose is the propositional function: For any
Then, using the above Lemma:
Now is self-evident.
So the result is proved, by Induction, for all
For the second part, we note that for all , and the result follows immediately.