|
Question 26646: Let (Fn)=(1,1,2,3,5,8,13,21,34,55,...) be the fibonacci sequence defined by
F1=F2=1, Fn=F(n-1)+F(n-2) if n>2.
Show that it holds for n which is greator and equal to 1.
Fn < 2^(n)
Answer by venugopalramana(3286)   (Show Source):
You can put this solution on YOUR website! LET US COMPARE THE GIVEN SERIES WITH A GEOMETRIC SERIES WHOSE WE CAN DO...
THE G.P IS ...1,2,4,8,16,.......WITH C.R. OF 2 AND A=1.
FIRSTLY WE FIND THAT THE GIVEN SERIES IS ALL POSITIVE NUMBERS AND INCREASING SERIES AFTER F2,SINCE EVERY TERM IS THE SUM OF PREVIOUS 2 TERMS WHICH ARE POSITIVE...JENCE..F2
NOW WE HAVE..
F1=1............................................G1=1.........F1=G1
F2=1............................................G2=2G1.......F2
F3=F1+F2
F4=F2+F3
....................................................................
.....................................................................
FN=F(N-2)+F(N-1)
------------------------------------------------------------------------
ADDING ALL THE ABOVE WE GET...(F1+F2+F3+F4+...+FN)<(G1+G2+G3+.....+GN)
BUT WE KNOW THAT
G1+G2+G3+.....+GN=1+2+4+8+.........2^(N-1)
A=1...R=2...SO...SUM IS ..A*(R^N-1)/(R-1)=1*(2^N-1)/(2-1)=2^N-1
HENCE
(F1+F2+F3+F4+...+FN)<(G1+G2+G3+.....+GN)=2^N-1<2^N...THEN OBVIOUSLY
FN<2^N
|
|
|
| |
