Question 2 19] The sequence of Fibonacci numbers has very interesting properties

Question

Question 2 19] The sequence of Fibonacci numbers has very interesting properties and is used in many great problems in science and mathematics. The Fibonacci sequence is defined as following: F1 = 1 F2-1 Fn = Fn-1+ Fn-2 for any n 3 That is, the first two numbers of the sequence are 1 and every other number is the sum of the previous two numbers in the sequence. So, the sequence looks like the following: 1, 1,2, 3, 5, 8, 13,21, 34,55, Using induction, prove the following property of the Fibonacci numbers: For any n> 1, Fn 2n

Explanation / Answer

Base case: n=1

F_1=1<2^1

So base case is true

Assume true for some n>=1

We show it is true for n+1

F_{n+1}=F_n+F_{n-1}<2^n+2^{n-1}<2^n+2^n=2*2^n=2^{n+1}

Hence true for n+1 and hence for all n>=1

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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