22.Question DetailsHunterDM3 5.5.024 Use a recurrence relation to show that Algo

Question

22.Question DetailsHunterDM3 5.5.024 Use a recurrence relation to show that Algorithm 5.19 w always return a sequence of 2" 1 ordered pairs. Let P(n) be the number of pairs returned by Hanoi (n, P1, P2). By the definition of Hanoi, one pair will be returned if n 1, and P(n 1)1P(n 1) pairs are returned when n>1. As a recurrence relation, if n1 P1)1 Pn 1) if n>1. P(n) = We now prove that P(n) 21 Proof. (Induction on n.) If n = 1, P(1)-1 = 21-1. Suppose as inductive hypothesis that P(k-1)-2k-1-1, for some k> 1. Then P(k)P(k 1)1+ P(k 1) 2k-1 + 1 2*-1-1 as required

Explanation / Answer

P(k) = P(k-1)+1+P(k-1)

= 2k-1 - 1 + 1 + 2k-1 - 1

= 2k - 1

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.