Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Fibonacci sequence question.. please help! 10pts!?
Okay, I have a practice questions I need help with to study for my exam. It deals with the fibonacci sequence.
We define the sequence like this (where "_" means subscript) :
F_0 = 0
F_1 = 1
F_n = F_(n-1) + F_(n-2)
The question I need to do is:
Prove: " F_n > F_(n-1) "
---------------------------------------------
I know that I need to substitute the formula for both sides, but I'm really confused how to prove this. Can anyone help? Thanks!
1 Answer
- Demiurge42Lv 71 decade agoFavorite Answer
F_2 = 1 which is not greater than F_1
So I assume then that you are supposed to prove "F_n > F_(n-1) for n > 2".
Use strong mathematical induction.
The base case is for n = 3.
F_3 = 2 > 1 = F_2
Assume that F_m > F_(m-1) for all 2 < m ≤ n (for all m greater than 2 and less than or equal to n)
You want to show that F_(n+1) > F_n given that the above is true.
F_(n+1) = F_n + F_(n-1) from the definition of the Fibonacci sequence.
F_(n+1) - F_n = F_(n-1)
But F_(n-1) > F_(n-2) > F_(n-3) > ... > F_3 = 2 by assumption
so F_(n+1) - F_n > 2 > 0
F_(n+1) > F_n
