Mathematics for Computer Science

15.6. References 655

for moving a stack ofnrings 2 poles forward. This is trivial fornD 0. Forn > 0,
define:

P 1 .n/: ApplyP 2 .n1/to move the topn 1 rings two poles forward to the third
pole. Then move the remaining big ring once to land on the second pole. Then
applyP 2 .n1/again to move the stack ofn 1 rings two poles forward from the
third pole to land on top of the big ring.

P 2 .n/: ApplyP 2 .n1/to move the topn 1 rings two poles forward to land on
the third pole. Then move the remaining big ring to the second pole. Then apply
P 1 .n1/to move the stack ofn 1 rings one pole forward to land on the first
pole. Now move the big ring 1 pole forward again to land on the third pole. Finally,
applyP 2 .n1/again to move the stack ofn 1 rings two poles forward to land
on the big ring.

Lettnbe the number of moves needed to solve the Sheboygan puzzle using proce-
dureP 1 .n/. Show that
tnD2tn 1 C2tn 2 C3; (15.22)

forn > 1.

Hint:Letunbe the number of moves used by procedureP 2 .n/. Express each oftn
andunas linear combinations oftn 1 andun 1 and solve fortn.

(e)Derive valuesa;b;c; ̨;ˇsuch that

tnDa ̨nCbˇnCc:

Conclude thattnDo.sn/.

Homework Problems

Problem 15.17.
Taking derivatives of generating functions is another useful operation. This is done
termwise, that is, if

F.x/Df 0 Cf 1 xCf 2 x^2 Cf 3 x^3 C


;

then
F^0 .x/WWDf 1 C2f 2 xC3f 3 x^2 C


:

For example,

1

.1x/^2

D



1

.1x/

 0

D 1 C2xC3x^2 C