9. (8) Here is an inefficient algorithm for computing F(N): F(n) if n s I return

Question

9. (8) Here is an inefficient algorithm for computing F(N): F(n) if n s I return n else return F(n-1)+ F(n-2) nce again I ask you to prove by induction something that Levitin derived by other means. The idea of this problem comes from Weiss Section 7.3. Use mathematical induction to show that the formula (in the last line of the Weiss excerpt below) is indeed the solution to the given recurrence (the recurrence in the next-to-last line of the following Weiss excerpt). Weiss Excerpt: Let C(N) be the number of calls to fib made during the evaluation of fib(n). Clearly C(0)-C(I)-I call. For N 22, we call fib(n),plus all the calls needed to evaluate fib(n-1) and fib(n-2) recursively and independently. Thus C(N)s C( N-I ) + C(N-2 ) +1 . By induction, we can easily verify that for N 23 the solution to this recurrence is CN)F+2+Fv-1-1.

Explanation / Answer

C(N) = C(N-1) + C(N-2) + 1

We need to prove the following:

C(N) = F(N+2) + F(N-1) - 1

The base case N = 3:
C(3) = F(5) + F(2) - 1    // 1 1 2 3 5 8

    = 8 + 2 - 1 = 9

    = F(3) + F(4) + F(0) + F(1) - 1
    = F(2) + F(1) + F(3) + F(2) + F(0) + F(1)
    = F(0) + F(1) + F(1) + F(2) + F(1) + F(1) + F(0) + F(0) + F(1)
    = F(0) + F(1) + F(1) + F(1) + F(0) + F(1) + F(1) + F(0) + F(0) + F(1) - 1
    = 9

   Hence base case holds

Assuming it is true for N = k

C(k) = F(k+2) + F(k-1) - 1

We will prove for

   C(k+1) = F(k+3) + F(k) - 1

Lets start with RHS

   C(k+1) = C(k) + C(k-1) + 1
          = F(k+2) + F(k-1) - 1 + F(k+1) + F(k-2) - 1 + 1
          = F(k+2) + F(k) - 1 + F(k+1) - 1 + 1
          = F(k+3) + F(k) -1 -1 + 1
          = F(k+3) + F(k) -1

Hence Proved

Related Questions

Navigate

• Browse (All)
• Browse 9
• Subjects

---

---

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