Maths Olympiad Prep

Library / /16 of 47

, 2013

Algebra Difficulty 2.1 Junior Prove it Canada

In the Fibonacci sequence, 1,1,2,3,5,1,1,2,3,5,\ldots, each term after the second is the sum of the previous two terms. How many of the first 100 terms of the Fibonacci sequence are odd?
In an arithmetic sequence, the sum of the first and third terms is 6 and the sum of the second and fourth terms is 20. Determine the tenth term in the sequence.

(An arithmetic sequence is a sequence in which each term after the first is obtained from the previous term by adding a constant. For example, 3,5,7,93, 5, 7, 9 are the first four terms of an arithmetic sequence.)

Solution

The parity of an integer is whether it is even or odd.

Since the Fibonacci sequence begins 1,1,2,3,5,8,13,21,1, 1, 2, 3, 5, 8, 13, 21, \ldots, then the parities of the first eight terms are Odd, Odd, Even, Odd, Odd, Even, Odd, Odd.

In the sequence, if xx and yy are consecutive terms, then the next term is x+yx+y.

In general, suppose that xx and yy are integers.

If xx is even and yy is even, then x+yx+y is even. If xx is even and yy is odd, then x+yx+y is odd.

If xx is odd and yy is even, then x+yx+y is odd. If xx is odd and yy is odd, then x+yx+y is even.

Therefore, the parities of two consecutive terms xx and yy in the Fibonacci sequence determine the parity of the following term x+yx+y.

Also, once there are two consecutive terms whose parities match the parities of two earlier consecutive terms in the sequence, then the parities will repeat in a cycle.

In particular, the parities of the fourth and fifth terms (Odd, Odd) are the same as the parities of the first and second terms (Odd, Odd).

Therefore, the parities in the sequence repeat the cycle Odd, Odd, Even.

This cycle has length 3.

Therefore, the 99th term in the Fibonacci sequence ends one of these cycles, since 99 is a multiple of 3.

In particular, the 99th term ends the 33rd cycle.

Each cycle contains two odd terms.

Therefore, the first 99 terms in the sequence include 2×33=662\times 33 = 66 odd terms.

Finally, the 100th term in the sequence begins a new cycle, so is odd.

Therefore, the first 100 terms include 66+1=6766+1=67 odd terms.
Suppose that the first term in the given sequence is aa and the common difference is dd.

Then the first four terms are a,a+d,a+2d,a+3da,a+d,a+2d,a+3d.

From the given information, a+(a+2d)=6a+(a+2d)=6 and (a+d)+(a+3d)=20(a+d)+(a+3d)=20.

The first equation simplifies to 2a+2d=62a+2d=6 or a+d=3a+d=3.

The second equation simplifies to 2a+4d=202a+4d=20 or a+2d=10a+2d=10.

Therefore, (a+2d)(a+d)=103(a+2d)-(a+d)=10-3 or d=7d=7.

Since a+d=3a+d=3 and d=7d=7, then a=4a=-4.

Therefore, the tenth term in the sequence is a+9d=4+9(7)=59a+9d=-4+9(7)=59.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.