- Give a definition of .
- Prove the following is true for :
- We define
Proof. The proof is by induction. For the case we have, on the left,
On the right,
Thus, the formula holds for the case . Assume then that it holds for some . Then we have,
Thus, the formula holds for if it holds for ; hence, we have shown that it holds for all