The next few exercises give recursive definitions of some familiar arithmetic operations which are usually defined nonrecursively. In each, you’re asked to prove a familiar property by structural...

The next few exercises give recursive definitions of some familiar arithmetic operations which are usually defined nonrecursively. In each, you’re asked to prove a familiar property by structural induction. Think carefully when you choose the quantity upon which to perform induction, and don’t skip any steps in your proof! You may use the elementary-school facts about addition and multiplication from Figure 5.39 in your proofs:

Let’s define an even number as either (i) 0, or (ii) 2 + k, where k is an even number. Prove by structural induction that the sum of any two even numbers is an even number

Figure 5.39: A few elementary-school facts about addition and multiplication.