Prove that for $n \geq 5, f_{n}+f_{n-1}-1$ has at least $n+1$ prime factors

Question

Question -

Prove that for $n \geq 5, f_{n}+f_{n-1}-1$ has at least $n+1$ prime factors, where $f_{n}=2^{2^{n}}+1$

My proof - I proved it using induction,but i got stucked in base case step,

for $n=5$ we get after lots of factoring that $f_{5}+f_{4}-1$ = $3 \cdot 7 \cdot 13 \cdot 241 .(2^{16}-2^8+1)$

Now i am not able to factor $(2^{16}-2^8+1)$ , i tried mod $3,7,19,13,9$ but none of them working ...

thankyou

Answer 1

Base case:

$n=5$

By the question and the comments, we get $$f_5+f_4+1=3\times7\times13\times97\times241\times673$$, so base case finished.

Let $p(n)$ be the number of distinct prime factors of $n$.

Assume the proposition is true for integer $k\ge5$, i.e. $$p(f_k+f_{k-1}+1)=p\Big(2^{2^{k+1}}+2^{2^k}+1\Big)\ge k+1$$. Then we let $K=2^{2^k}$.

So $$p(f_k+f_{k-1}+1)=p\big(K^2+K+1\big)\ge k+1$$

When $n=k+1$,

$$p(f_{k+1}+f_{k}+1)=p\big(K^4+K^2+1\big)= p\Big(\big(K^2+K+1\big) \big(K^2-K+1\big) \Big)$$. As the number of distinct prime factors of $K^2+K+1 $ is larger than $k+1$, also $K^2+K+1$ and $K^2-K+1$ are coprime, so $K^2-K+1$ has at least one prime factor which is not a prime factor of $K^2+K+1$, so $$p(f_{k+1}+f_{k}+1)=p\big(K^4+K^2+1\big)\ge k+1+1=k+2 $$, as desired.