For $n\ge4,$ prove that $F_n+1$ is not prime, where $F_n$ is $n^{th}$ Fibonacci number
What is the idea of the proof? I tried it by contradiction by letting $(1+F_n)$ to be prime $\implies$ $F_n$ is not prime $\implies$ WHAT NEXT?
For $n\ge4,$ prove that $F_n+1$ is not prime, where $F_n$ is $n^{th}$ Fibonacci number
What is the idea of the proof? I tried it by contradiction by letting $(1+F_n)$ to be prime $\implies$ $F_n$ is not prime $\implies$ WHAT NEXT?
As observed by Will Jagy we can always write $F_n+1$ as a product of a Fibonacci number and a Lucas number.
Let $\phi=(1+\sqrt5)/2$. It is well known that then $$ F_n=\frac1{\sqrt5}(\phi^n-(-\phi)^{-n}) $$ and $$ L_n=(\phi^n+(-\phi)^{-n}). $$ Both these sequences of integers satisfy the famous two-step recurrence relation, the difference coming from the initializations $F_0=0, F_1=1$ as opposed to $L_0=2, L_1=1$.
The following factorizations then follow immediately from $F_1=F_2=1$. $$ \begin{aligned} F_{2k+1}L_{2k}&=F_{4k+1}+F_1=F_{4k+1}+1,\\ F_{2k-1}L_{2k}&=F_{4k-1}+F_1=F_{4k-1}+1,\\ F_{2k}L_{2k-2}&=F_{4k-2}+F_2=F_{4k-2}+1,\\ F_{2k-1}L_{2k+1}&=F_{4k}+F_2=F_{4k}+1. \end{aligned} $$ All the residue classes modulo $4$ were covered, so the claim follows.
As an example: $$ \begin{aligned} F_{2k-1}L_{2k+1}&=\frac1{\sqrt5}(\phi^{2k-1}+\phi^{-(2k-1)})(\phi^{2k+1}-\phi^{-(2k+1)})\\ &=\frac1{\sqrt5}(\phi^{4k}+\phi^2-\phi^{-2}-\phi^{-4k})\\ &=F_{4k}+F_2=F_{4k}+1. \end{aligned} $$ It's all about polynomials of $\phi$. You do need to be careful with the parities of the exponents due to that $-\phi$ in the base.
Citing a proof of $F_n \pm 1$ not being a prime by tastymath75025 from AoPS forum: https://artofproblemsolving.com/community/c4h1249887p8924937
Lemma: If $n$ is odd, then $F_n^2-1=F_{n-1}F_{n+1}$.
Lemma 2: If $n$ is even, then $F_n^2-1=F_{n-2}F_{n+2}$.
Proof: For each statement either induct on $n$ or just use Binet's formula.
Now, if $n$ is odd then $(F_n-1)(F_n+1)=F_{n-1}F_{n+1}$. Clearly $F_n-1$ is not prime because $F_n-1 > F_{n-1}$ and $F_n-1 < F_{n+1} < 2(F_n-1)$, so $F_n-1$ cannot divide either factor on the RHS. Similar reasoning finishes for $F_n+1$.
Now, if $n$ is even then $(F_n-1)(F_n+1)=F_{n-2}F_{n+2}$. If $F_n-1$ is prime then clearly it must divide $F_{n+2}$ and not $F_{n-2}$. But it's easy to show $2(F_n-1) < F_{n+2} < 3(F_n-1)$, contradiction, and similarly for $F_n+1$.
As @lhf pointed out in comments, first two lemmas are known as Cassini and Catalan's identities. Also worth adding that $F_{n+1} < 2(F_n-1)$ is true for $n\geq 6$, while $F_{n+2} < 3(F_n-1)$ for $n\geq 7$. Rest of the cases can be checked by hand.
Apparently one and only one way to factor as a Lucas times a Fibonacci number.
Sun May 13 13:02:30 PDT 2018
4 1 + F 6 = 3 * 2 Lucas index 2 Fibonacci index 2
5 1 + F 9 = 3 * 3 Lucas index 2 Fibonacci index 3
6 1 + F 14 = 7 * 2 Lucas index 4 Fibonacci index 2
7 1 + F 22 = 11 * 2 Lucas index 5 Fibonacci index 2
8 1 + F 35 = 7 * 5 Lucas index 4 Fibonacci index 4
9 1 + F 56 = 7 * 8 Lucas index 4 Fibonacci index 5
10 1 + F 90 = 18 * 5 Lucas index 6 Fibonacci index 4
11 1 + F 145 = 29 * 5 Lucas index 7 Fibonacci index 4
12 1 + F 234 = 18 * 13 Lucas index 6 Fibonacci index 6
13 1 + F 378 = 18 * 21 Lucas index 6 Fibonacci index 7
14 1 + F 611 = 47 * 13 Lucas index 8 Fibonacci index 6
15 1 + F 988 = 76 * 13 Lucas index 9 Fibonacci index 6
16 1 + F 1598 = 47 * 34 Lucas index 8 Fibonacci index 8
17 1 + F 2585 = 47 * 55 Lucas index 8 Fibonacci index 9
18 1 + F 4182 = 123 * 34 Lucas index 10 Fibonacci index 8
19 1 + F 6766 = 199 * 34 Lucas index 11 Fibonacci index 8
20 1 + F 10947 = 123 * 89 Lucas index 10 Fibonacci index 10
21 1 + F 17712 = 123 * 144 Lucas index 10 Fibonacci index 11
22 1 + F 28658 = 322 * 89 Lucas index 12 Fibonacci index 10
23 1 + F 46369 = 521 * 89 Lucas index 13 Fibonacci index 10
24 1 + F 75026 = 322 * 233 Lucas index 12 Fibonacci index 12
25 1 + F 121394 = 322 * 377 Lucas index 12 Fibonacci index 13
26 1 + F 196419 = 843 * 233 Lucas index 14 Fibonacci index 12
27 1 + F 317812 = 1364 * 233 Lucas index 15 Fibonacci index 12
28 1 + F 514230 = 843 * 610 Lucas index 14 Fibonacci index 14
29 1 + F 832041 = 843 * 987 Lucas index 14 Fibonacci index 15
30 1 + F 1346270 = 2207 * 610 Lucas index 16 Fibonacci index 14
31 1 + F 2178310 = 3571 * 610 Lucas index 17 Fibonacci index 14
32 1 + F 3524579 = 2207 * 1597 Lucas index 16 Fibonacci index 16
33 1 + F 5702888 = 2207 * 2584 Lucas index 16 Fibonacci index 17
34 1 + F 9227466 = 5778 * 1597 Lucas index 18 Fibonacci index 16
35 1 + F 14930353 = 9349 * 1597 Lucas index 19 Fibonacci index 16
36 1 + F 24157818 = 5778 * 4181 Lucas index 18 Fibonacci index 18
37 1 + F 39088170 = 5778 * 6765 Lucas index 18 Fibonacci index 19
38 1 + F 63245987 = 15127 * 4181 Lucas index 20 Fibonacci index 18
39 1 + F 102334156 = 24476 * 4181 Lucas index 21 Fibonacci index 18
40 1 + F 165580142 = 15127 * 10946 Lucas index 20 Fibonacci index 20
41 1 + F 267914297 = 15127 * 17711 Lucas index 20 Fibonacci index 21
42 1 + F 433494438 = 39603 * 10946 Lucas index 22 Fibonacci index 20
43 1 + F 701408734 = 64079 * 10946 Lucas index 23 Fibonacci index 20
44 1 + F 1134903171 = 39603 * 28657 Lucas index 22 Fibonacci index 22
Sun May 13 13:02:30 PDT 2018
For all $n=3k,3k+1$, $F_n$ will be odd. Which means $F_n+1$ will be even
Still trying for $n=3k+2$ when $F_n$ will be even.
PS: $F_1=1$