# Fibonacci[n]-1 is always composite for n>6. why?

In[11]:= Select[Table[Fibonacci[n], {n, 1, 10000}], PrimeQ[# - 1] &]

Out[11]= {3, 8}

Edit: Fibonacci[n]-1 is always composite for n>6. why? $$\sum\limits_{i = 0}^n {{F_i}} = {F_{n + 2}} - 1$$

In[16]:= Select[Table[Fibonacci[n], {n, 1, 10000}], PrimeQ[# + 1] &]

Out[16]= {1, 1, 2}

Fibonacci[n]+1 is always composite for n>3. why?

-
Please improve the question's readability. Perhaps add the title into the body as well. – Asaf Karagila Jan 9 '11 at 10:23
This question is relevant to my interests – Listing Jan 9 '11 at 12:04
"Always" is not the same as "holds true in the first 10,000 cases" in mathematics. Also, are you sure you enabled arbitrary precision arithmetic to do this computation? – Qiaochu Yuan Jan 9 '11 at 13:53
@Qiaochu: Mathematica uses exact integers to do all this. – Mariano Suárez-Alvarez Jan 9 '11 at 14:35
@Mariano: I wasn't sure what language this was, and when I tried to duplicate the results in Matlab I ran into the precision problem, so I thought it was worth mentioning. – Qiaochu Yuan Jan 9 '11 at 14:53

mjqxxxx is correct; there is a proof in Honsberger's Mathematical Gems III, which is short enough to reproduce here. In fact, it suffices to verify the following eight identities:

$$F_{4k} - 1 = F_{2k+1} L_{2k-1}$$ $$F_{4k+1} - 1 = F_{2k} L_{2k+1}$$ $$F_{4k+2} - 1 = F_{2k} L_{2k+2}$$ $$F_{4k+3} - 1 = F_{2k+2} L_{2k+1}$$ $$F_{4k} + 1 = F_{2k-1} L_{2k+1}$$ $$F_{4k+1} + 1 = F_{2k+1} L_{2k}$$ $$F_{4k+2} + 1 = F_{2k+2} L_{2k}$$ $$F_{4k+3} + 1 = F_{2k+1} L_{2k+2}$$

where $L_k$ are the Lucas numbers. These identities all follow straightforwardly from Binet's formula, although I imagine there are also combinatorial proofs.

I suspect at least one of these is an open problem, if not both. Let me record for now the following observation: modular arithmetic is not enough.

Proposition: For any finite set $p_1, ... p_n$ of primes, there exists a Fibonacci number $F_k$ such that $\prod p_i | F_k$.

Proof. Since $F_n | F_{mn}$ for all $m, n \ge 1$ it suffices to show this for a single prime. But the Fibonacci sequence is clearly periodic $\bmod p$ for any $p$ (since the Fibonacci recursion is reversible), and $F_0 = 0 \equiv 0 \bmod p$. (The computation of the exact period $\bmod p$ is a nice exercise.)

So both $F_n + 1$ and $F_n - 1$ can avoid any finite set of primes.

-
Your proposition is lacking a product symbol (at least in my browser) – TonyK Jan 9 '11 at 14:12
@TonyK: there's an implied quantifier on i. But I guess I might as well be more precise. – Qiaochu Yuan Jan 9 '11 at 14:15
Implied quantifier? Fellow thinks he's Einstein. Anyway, +1 for listening :-) – TonyK Jan 9 '11 at 14:51
I find an identity in a paper just now. $F_n^2-F_{n-1}F_{n+1}=(-1)^{n-1}$ fq.math.ca/Scanned/8-1/daykin-a.pdf – a boy Jan 10 '11 at 3:25

Wikipedia cites the following source for the assertion that no sufficiently large Fibonacci number is one greater or one less than a prime:

Ross Honsberger, Mathematical Gems III (AMS Dolciani Mathematical Expositions No. 9), 1985, ISBN 0-88385-318-3, p. 133.

Not sure if that reference has a proof.

-
It does! I'm surprised. I'll add it to my answer and make it CW. – Qiaochu Yuan Jan 9 '11 at 17:19