The sequence of Fibonacci numbers has very interesting properties and is used in

Question

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

for n = 1 , the inequality holds
F(1) = 1 < 2*1 = 2

for some n ,
Let F(n) < 2*n
for , n+1
F(n+1) = F(n) + F(n-1)
Now , F(n) < 2*n && F(n-1) < 2*n-2
therefore ,
F(n+1) < 4*n - 2
F(n+1) < 2*n + 2 + 2*n - 4

Now , 2*n - 4 >= 0 for n >= 2
Hence ,
F(n+1) < 2*(n+1)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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