Maths Olympiad Prep

Library / /46 of 86

Algebra Difficulty 6.8 National Olympiad Prove it United States

Problem:

The Fibonacci sequence is the list of numbers that begins 11, 22, 33, 55, 88, 1313 and continues with each subsequent number being the sum of the previous two.
Prove that when the first nn elements of the Fibonacci sequence are alternately added and subtracted, the result is an element of the sequence or the negative of an element of the sequence. For example,
12+35=3 1-2+3-5=-3
and 33 is an element of the Fibonacci sequence.

Solution

Solution:

Expanding each number as the sum of the two previous numbers gives, for example,
12+35+813=1(1+1)+(1+2)(2+3)+(3+5)(5+8). 1-2+3-5+8-13=1-(1+1)+(1+2)-(2+3)+(3+5)-(5+8)\text{.}
Now, after removing parentheses, this is a telescoping series: each term subtracts out with its neighbor, so what's left is the last term of this expanded sum, or the second-to-last term of the original sum.
=111+1+223+3+558=8. =1-1-1+1+2-2-3+3+5-5-8=-8\text{.}
To make it clear that this pattern always works, it would be nice to write all of this in terms of FnF_n, the nthn^{\text{th}} number in the list. When doing so, the previous expression becomes
F1F2+F3±Fn=(F1)(F0+F1)+(F1+F2)±(Fn2+Fn1) F_1-F_2+F_3-\ldots \pm F_n=\left(F_1\right)-\left(F_0+F_1\right)+\left(F_1+F_2\right)-\ldots \pm\left(F_{n-2}+F_{n-1}\right)
and so this works for all nn because F0=F1F_0=F_1, so every pair of consecutive terms in this long expression adds up to 00, except for the Fn1F_{n-1} at the end.

Pair up the terms. For our example above,
12+35+813=(12)+(35)+(813)=1+2+5, 1-2+3-5+8-13=(1-2)+(3-5)+(8-13)=1+2+5,
which shows that after the initial 11 we get every other term of the sequence. Then, we add, with 1+2=31+2=3, and then 3+5=83+5=8. To make it clear that this pattern always works, you will need to consider examples with an odd number of terms as well as showing that F1+F2+F4++F2n=F2n+1F_1+F_2+F_4+\ldots+F_{2n}=F_{2n+1}.
Other good arguments include a proof by mathematical induction, which supposes that this pattern works for the sum up to FnF_n and then proves that it continues working for the sum up to Fn+1F_{n+1}.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.