For $n\ge4,$ prove that $F_n+1$ is not prime, where $F_n$ is $n^{th}$ Fibonacci number. 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?
 A: 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.
A: 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.
A: 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$
