Fibonacci Seven

Probability Level 3

Fibonacci numbers are given by the following recursion relation:

$\begin{cases} F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2}\text{ for }n>1 \end{cases}$

If the fraction of Fibonacci numbers that are divisible by 7 is given by $\dfrac{a}{b}$ , where $a$ and $b$ are coprime positive integers, what is $a+b$ ?

The answer is 9.

1 solution

Geoff Pilling
Jun 20, 2017

If we take the Fibonacci numbers modulo $7$ , we get the following series:

$0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0 , 1, 1, 2, ...$

The series repeats every $16$ numbers, and every set of $16$ contains two zeros which represent numbers divisible by $7$ .

So, the fraction of Fibonacci numbers divisible by $7$ is given by:

$\dfrac{2}{16} = \dfrac{1}{8}$

$1+8 = \boxed9$

Interesting question! There are some fascinating divisibility properties in the Fibonacci sequence - every third Fibonacci number is even and every fifth is divisible by $5$ , for instance. I'm thinking there's a way to prove by induction that every eighth Fibonacci number is divisible by $7$ .

Zach Abueg - 3 years, 11 months ago

Ah, there might be... Lemme think about it for a bit...

Geoff Pilling - 3 years, 11 months ago

Fibonacci Seven

The answer is 9.

1 solution

0 pending reports