Tower of Hanoi with Adjacency Requirement: Suppose the same situation as in exercise 17

Chapter 5, Problem 18

(choose chapter or problem)

Tower of Hanoi with Adjacency Requirement: Suppose the same situation as in exercise 17. Let

.

a. Find \(b_{1}, b_{2}, and b_{3}\).

b. Find \(b_{4}\).

c. Show that \(b_{k} = a_{k−1} + 1 + b_{k−1}\) for all integers k ≥ 2, where \(a_{1}, a_{2}, a_{3}\), . . . is the sequence defined in exercise 17.

d. Show that \(b_{k} ≤ 3b_{k−1} + 1\) for all integers k ≥ 2.

e. Show that \(b_{k} = 3b_{k−1} + 1\) for all integers k ≥ 2.

Text Transcription:

b_1, b_2, and b_3

b_4

b_k = a_k−1 + 1 + b_k−1

a_1, a_2, a_3

b_k ≤ 3b_k−1 + 1

b_k = 3b_k−1 + 1