Mathematics for Computer Science

Chapter 6 Induction142

and a binary digit,cnC 1 , as outputs, and satisfies the specification:

num. ̨n/Cnum.ˇn/Cc 0 D 2 nC^1 cnC 1 Cnum.n/: (6.8)

There is a straighforward way to implement annC 1 -bit adder as a digital circuit:
annC 1 -bitripple-carry circuithas 1 C2.nC1/binary inputs

an;:::;a 1 ;a 0 ;bn;:::;b 1 ;b 0 ;c 0 ;

andnC 2 binary outputs,
cnC 1 ;sn;:::;s 1 ;s 0 :

As in Problem 3.5, the ripple-carry circuit is specified by the following formulas:

siWWDai XOR bi XOR ci (6.9)

ciC 1 WWD.ai ANDbi/OR.ai AND ci/OR.bi ANDci/;: (6.10)

for 0 in.

(a)Verify that definitions (6.9) and (6.10) imply that

anCbnCcnD2cnC 1 Csn: (6.11)

for alln 2 N.

(b)Prove by induction onnthat annC 1 -bit ripple-carry circuit really is annC 1 -
bit adder, that is, its outputs satisfy (6.8).

Hint:You may assume that, by definition of binary representation of integers,

num. ̨nC 1 /DanC 12 nC^1 Cnum. ̨n/: (6.12)

Problem 6.8.
The Math for Computer Science mascot, Theory Hippotamus, made a startling
discovery while playing with his prized collection of unit squares over the weekend.
Here is what happened.
First, Theory Hippotamus put his favorite unit square down on the floor as in
Figure 6.9 (a). He noted that the length of the periphery of the resulting shape was
4, an even number. Next, he put a second unit square down next to the first so that
the two squares shared an edge as in Figure 6.9 (b). He noticed that the length
of the periphery of the resulting shape was now 6, which is also an even number.
(The periphery of each shape in the figure is indicated by a thicker line.) Theory
Hippotamus continued to place squares so that each new square shared an edge