In Example 5.11, we showed the correctness of the parity function (see Figure 5.25)—that is, for any n ≥ 0, we have that parity(n) = n mod 2. Prove by strong induction on n that the depth of the...

In Example 5.11, we showed the correctness of the parity function (see Figure 5.25)—that is, for any n ≥ 0, we have that parity(n) = n mod 2. Prove by strong induction on n that the depth of the recursion (that is, the total number of calls to parity made) for parity(n) is 1 + ⌊n/2⌋.