Maths Olympiad Prep

Library / /511 of 520

Algebra Difficulty 7.7 National olympiad, round 2 Prove it

1. Use mathematical induction to prove the following general term formula for the Fibonacci sequence: for n1n \geqslant 1
Fn=(1+5)n(15)n2n5F_{n}=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n} \sqrt{5}}

and prove that, for n1n \geqslant 1,
Fn=[(1+52)n/2]+CnF_{n}=\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n} / 2\right]+C_{n}

where [a][a] denotes the greatest integer not exceeding aa, and Cn=1C_{n}=1 or 0 depending on whether nn is odd or even.

Solution

1. Proof: Since F1=F2=1F_{1}=F_{2}=1, (91) holds for n=1n=1. Now assume (91) holds for 1nk1 \leqslant n \leqslant k, we consider the case n=k+1n=k+1. By equation (8) in this chapter, we have
Fk+1=Fk+Fk1=(1+5)k(15)k+2(1+5)k12(15)k12k5=(1+5)k+12k+15(21+52(15)k(1+5)k+1+4(1+5)24(15)k1(1+5)k+1)=(1+5)k+12k+15(1(15)k1(1+5)k+1(625))=(1+5)k+12k+15(1(15)k+1(1+5)k+1)=(1+5)k+1(15)k+12k+15,\begin{array}{c} F_{k+1}=F_{k}+F_{k-1} \\ =\frac{(1+\sqrt{5})^{k}-(1-\sqrt{5})^{k}+2(1+\sqrt{5})^{k-1}-2(1-\sqrt{5})^{k-1}}{2^{k} \sqrt{5}} \\ =\frac{(1+\sqrt{5})^{k+1}}{2^{k+1} \sqrt{5}}\left(\frac{2}{1+\sqrt{5}}-\frac{2(1-\sqrt{5})^{k}}{(1+\sqrt{5})^{k+1}}\right. \\ \left.+\frac{4}{(1+\sqrt{5})^{2}}-\frac{4(1-\sqrt{5})^{k-1}}{(1+\sqrt{5})^{k+1}}\right) \\ =\frac{(1+\sqrt{5})^{k+1}}{2^{k+1} \sqrt{5}}\left(1-\frac{(1-\sqrt{5})^{k-1}}{(1+\sqrt{5})^{k+1}}(6-2 \sqrt{5})\right) \\ =\frac{(1+\sqrt{5})^{k+1}}{2^{k+1} \sqrt{5}}\left(1-\frac{(1-\sqrt{5})^{k+1}}{(1+\sqrt{5})^{k+1}}\right) \\ =\frac{(1+\sqrt{5})^{k+1}-(1-\sqrt{5})^{k+1}}{2^{k+1} \sqrt{5}}, \end{array}

This proves that (91) holds for n=k+1n=k+1, thus (91) is proved.
Notice that for n1n \geqslant 1 we have
51>0\sqrt{5}-1>0

and
(51)n<2n(\sqrt{5}-1)^{n}<2^{n}

Thus, we always have
0<(51)n52n<10<\frac{(\sqrt{5}-1)^{n}}{\sqrt{5} \cdot 2^{n}}<1

Since FnF_{n} 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.