 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