The definition of the Fibonacci numbers is as follows: F(0)=0 F(1)=1 F(n)=F(n-2)

Question

The definition of the Fibonacci numbers is as follows: F(0)=0 F(1)=1 F(n)=F(n-2)+F(n-1) for n 2 Prove the given property of the Fibonacci numbers directly from the definition (hint: do a direct proof): F(n + 3) = 2F(n + 1) + F(n) for n 0 Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F( 1) occur? Show all work

Explanation / Answer

1.) f(n+3) = 2f(n+1) + f(n) for n>0 given f(n) = f(n-2)+f(n-1) so f(n+3) = f(n+3-2)+f(n+3-1) f(n+3) = f(n+1)+f(n+2) ---- 2 f(n+2) = f(n+2-2)+f(n+2-1) f(n+2) = f(n+1)+f(n) ---- 1 substitute 1 in 2 f(n+3) = f(n+1) + f(n+1) + f(n) f(n+3) = 2f(n+1) + f(n) Hence proved 2.) to calculate f(4) , we need to calculate f(3) and f(2) first to calculate f(3) we have to calculate f(2) and f(1) to calculate f(2) we have to calculate f(1) and f(0) so total f(1) calls = 1 + 2 = 3

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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