Fibonacci Number Proof


by ryou00730
Tags: fibonacci, number, proof
ryou00730
ryou00730 is offline
#1
Nov8-10, 11:05 AM
P: 29
1. The problem statement, all variables and given/known data
The Fibonacci numbers are defined recusively by:
F(0) = 0, F(1) = 1, for n > 1, F(n) = F(n − 1) + F(n − 2).
Use strong induction to show that F(n) < 2^n for all n.


2. Relevant equations
n/a

3. The attempt at a solution
I use my base case as F(2) = F(1) + F(0) = 1 which is less than 2^n = 2^2 = 4. After that I am not sure where to go with strong induction...
Phys.Org News Partner Science news on Phys.org
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance
micromass
micromass is offline
#2
Nov8-10, 11:21 AM
Mentor
micromass's Avatar
P: 16,510
The induction hypthesis gives us

[tex]F(n)=F(n-1)+F(n-2)\leq 2^{n-1}+2^{n-2}[/tex]

Can you now prove that this is smaller then [tex]2^n[/tex]?
ryou00730
ryou00730 is offline
#3
Nov8-10, 01:04 PM
P: 29
well 2^n-1 + 2^n-2 is equal to 2^n (2^-1 + 2^-2) = 3/4(2^n) but I don't see the logic behind equating the problem to less than or equal to 2^n-1 + 2^n-2

micromass
micromass is offline
#4
Nov8-10, 01:12 PM
Mentor
micromass's Avatar
P: 16,510

Fibonacci Number Proof


If you want to apply induction? Then what is the induction hypothesis?
ryou00730
ryou00730 is offline
#5
Nov8-10, 01:15 PM
P: 29
Let k>2, for all integers i, with 2<=i<k, F(i)<2^i would be my induction hypothesis I think?
micromass
micromass is offline
#6
Nov8-10, 01:19 PM
Mentor
micromass's Avatar
P: 16,510
Yes, that is correct. So in particular, we have

[tex]F(n-1)\leq 2^{n-1}~\text{and}~F(n-2)\leq 2^{n-2}[/tex]

So

[tex]F(n-1)+F(n-2)\leq 2^{n-1}+2^{n-2}[/tex]
ryou00730
ryou00730 is offline
#7
Nov8-10, 01:20 PM
P: 29
woops, I meant n>2, so just replace all my k's with n's and so if I know that F(i)<2^i, then F(i-1) + F(i-2) < 2^i-1 + 2^i-2 which is F(i) < 3/4 2^i, so therefore F(i) must also be less than 2^i if its less than 0.75 of it, so the statement is true for all F(n)
ryou00730
ryou00730 is offline
#8
Nov8-10, 01:21 PM
P: 29
does that look about right?
micromass
micromass is offline
#9
Nov8-10, 01:25 PM
Mentor
micromass's Avatar
P: 16,510
Yeah, that looks fine
ryou00730
ryou00730 is offline
#10
Nov8-10, 01:27 PM
P: 29
thank you :), so in general with strong induction, you prove a base, then your induction hypothesis is that it works for all numbers between your base up until some value n, and you have to prove using this, that it also works for the n? thank you for all your help!
micromass
micromass is offline
#11
Nov8-10, 01:33 PM
Mentor
micromass's Avatar
P: 16,510
Yep, that is the idea behind strong induction.

Good luck with your next problems!
ryou00730
ryou00730 is offline
#12
Nov8-10, 01:34 PM
P: 29
thank you:)


Register to reply

Related Discussions
Find the previous Fibonacci number: java Engineering, Comp Sci, & Technology Homework 3
Fibonacci proof by induction Calculus & Beyond Homework 13
Fibonacci Proof with Induction Calculus & Beyond Homework 1
Fibonacci Number Crunch Calculus & Beyond Homework 1
Explicit Formula for the nth Fibonacci Number Introductory Physics Homework 12