Fibonacci sequence is defined by f(1)=1,f(2)=1 and f(m) =f(m-1)+f(m-2) i.e. 1, 1, 2, 3, 5, 8, 13, ...
Prove that for all composite values of n>4, f(n) is composite.

What follows is MUCH easier to show by a table than by description - no doubt any errors of expression will be quickly noted and corrected!

1.       There are various ways of writing the Fibonacci numbers.

If n = 3, f(n) = 2, or 2*1+1*0. Algebraically,  f(3)*m₁+f(2)*m₂

If n = 4 f(n) = 3, or 2*1+1*1 which is also 3*1+1*0

If n = 5, f(n) = 5, or 2*2+1*1 which is also 3*1+2*1, or 5*1+3*0

If n = 6 f(n) = 8; 2*3+1*2; 3*2+2*1; 5*1+3*1; 8*1+5*0

If n = 7, f(n) = 13; 2*5+1*3; 3*3+2*2; 5*2+3*1; 8*1+5*1; 13*1+8*0

and so on.  It is clear that m₁ and m₂ are also in the Fibonacci sequence, so that f(n) = f(3)*f(n-2)+f(2)*f(n-3)=f(4)*f(n-3)+f(3)*(n-4)=f(5)*f(n-4)+f(4)*f(n-5) etc., for sufficiently large n; generally, f(n) = f(x)*f(n-x+1) +f(x-1)*f(n-x) - for sufficiently large n.

 

2.       For clarity of exposition, let n = 3, f(x)=2 for f(n) = f(x)*f(n-x+1) +f(x-1)*f(n-x). The first part of the expression, f(x)*f(n-x+1) is clearly divisible by 2. Also,  f(x-1) = 1 and f(n-x) = 0, giving 0 as the value of the second part of the expression, so that the whole is divisible by 2. Now let n = 6; we need only evaluate the second part of the expression: f(x-1) is still 1; f(n-x) is f(3), which is already shown to be even. since any yet higher multiple will simply incorporate the lower (even) multiple, it follows immediately that if n is a multiple of 3, the second part of the expression will always be even.

 

3.       By parity of reasoning, if n=4 or a multiple of 4, f(n) must be a multiple of 3; if n=5 or a multiple of 5, f(n) must be a multiple of 5; if n = 6 or a multiple of 6, f(n) must be a multiple of 8; and so on.

 

4.       The function f(n) = f(x)*f(n-x+1) +f(x-1)*f(n-x) therefore works as a kind of sieve of Eratosthenes over the Fibonacci sequence, with the exception of the number 2. In other words, for n >4 f(n) is composite,  unless both :

 

a.       n is singly divisible by 2; and

b.      n is not a multiple of 3, or any larger number than 3;

5.    Hence, it appears to be necessary, although not sufficient, for n to be prime, if f(n) is to be prime also.

Edited on July 22, 2010, 1:17 pm

Posted by broll on 2010-07-22 10:12:40