Consider the algorithm in Figure 5.25, which finds the binary representation of a given integer n ≥ 0. For example, toBinary(13) = h1, 1, 0, 1i, and 1 2 3 + 1 2 2 + 0 2 1 + 1 2 0 = 8 + 4 + 0 + 1 = 13....

Consider the algorithm in Figure 5.25, which finds the binary representation of a given integer n ≥ 0. For example, toBinary(13) = h1, 1, 0, 1i, and 1 2 3 + 1 2 2 + 0 2 1 + 1 2 0 = 8 + 4 + 0 + 1 = 13. Prove the correctness of toBinary by strong induction—that is, prove that for any n ≥ 0, we have ∑ k i=0 bi2 i = n where toBinary(n) = hbk , . . . , b0i.

Your proof of the correctness of toBinary(n) establishes that any nonnegative integer can be represented in binary. Now you’ll show that this binary representation is unique—or, at least, unique up to leading zeros. (For example, we can represent 7 in binary as 111 or 0111 or 00111, but only 111 has no leading zeros.)

Figure 5.25: A reminder of the parity algorithm (from Figure 5.16), and an algorithm to convert an integer to binary