Mathematics for Computer Science

6.4. Strong Induction vs. Induction vs. Well Ordering 157

statesWWDN^3

start stateWWD.a;b;1/ (wherea > b > 0)

transitionsWWDif min.x;y/ > 0;then.x;y;e/!

the first possible state according to the rules:

8

ˆˆ

ˆˆˆ

ˆˆˆ

ˆˆˆ

<

ˆˆ

ˆˆˆ

ˆˆ

ˆˆˆ

ˆ:

.1;0;ex/ (ifxDy)

.1;0;e/ (ifyD 1 );

.x=2;y=2;2e/ (if 2 jxand 2 jy);

.y;x;e/ (ify > x)

.x;y=2;e/ (if 2 jy)

.x=2;y;e/ (if 2 jx)

.xy;y;e/ (otherwise):

(a)Prove that if this machine reaches a “final” state.x;y;e/in which no transition
is possible, theneDgcd.a;b/.

(b)Prove that the machine reaches a final state in at most 3 C 2 log max.a;b/
transitions.

Hint:Strong induction on max.a;b/.

Exam Problems

Problem 6.28.
Thenth Fibonacci number,Fn, is defined recursively as follows:

FnD

8

<

:

0 ifnD 0

1 ifnD 1

Fn 1 CFn 2 ifn 2

These numbers satisfy many unexpected identities, such as

F 02 CF 12 C


CFn^2 DFnFnC 1 (6.18)

Equation (6.18) can be proved to hold for alln 2 Nby induction, using the equation
itself as the induction hypothesis,P.n/.

(a)Prove thebase case.nD 0 /.

(b)Now prove theinductive step.