AlgebraDifficulty 7.7National olympiad, round 2Prove it
1. Use mathematical induction to prove the following general term formula for the Fibonacci sequence: for n⩾1 Fn=2n5(1+5)n−(1−5)n
and prove that, for n⩾1, Fn=[(21+5)n/2]+Cn
where [a] denotes the greatest integer not exceeding a, and Cn=1 or 0 depending on whether n is odd or even.
Solution
1. Proof: Since F1=F2=1, (91) holds for n=1. Now assume (91) holds for 1⩽n⩽k, we consider the case n=k+1. By equation (8) in this chapter, we have Fk+1=Fk+Fk−1=2k5(1+5)k−(1−5)k+2(1+5)k−1−2(1−5)k−1=2k+15(1+5)k+1(1+52−(1+5)k+12(1−5)k+(1+5)24−(1+5)k+14(1−5)k−1)=2k+15(1+5)k+1(1−(1+5)k+1(1−5)k−1(6−25))=2k+15(1+5)k+1(1−(1+5)k+1(1−5)k+1)=2k+15(1+5)k+1−(1−5)k+1,
This proves that (91) holds for n=k+1, thus (91) is proved. Notice that for n⩾1 we have 5−1>0
and (5−1)n<2n
Thus, we always have 0<5⋅2n(5−1)n<1
Since Fn is a positive integer, (92) holds.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.