Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is how to find all solutions $(m,n)\in\mathbb N^2$ for $F_n=f_m$, where $F_n=2^{2^n}+1$ and $f_m$ is the $m$th fibonacci number: $f_0=0$, $f_1=1$ and $f_n+f_{n+1}=f_{n+2}$ for each $n\in\mathbb N$.

Maybe this topic can give some inspiration for proving that there are no solutions for $m>5$: Fibonacci[n]-1 is always composite for n>6. why?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

$f_4 = 2^{2^0} + 1$ and $f_5 = 2^{2^1} + 1$, but I suspect that there is no $m > 5$ such that $f_m - 1$ is a power of $2$, let alone $2$ to a power of $2$. A search of $m \le 100000$ yields none.

EDIT: It appears that the least $m>2$ such that $f_m - 1$ is divisible by $2^j$ is $3 \times 2^{j-1} - 1$ for $j \ge 2$. Since those $f_m - 1$ are also divisible by $3$ for $j \ge 4$ (in fact $f_m \equiv 1 \mod 3$ for $m \equiv -1 \mod 8$), they are not powers of $2$.

EDIT: Let $m(j) = 3 \times 2^{j-1} - 1$. I claim that for $j \ge 2$ $$ \eqalign{f_{m(j)} &\equiv 1 + 2^j \mod 2^{j+1} \cr f_{m(j)+1} &\equiv 0 \mod 2^{j+1}\cr}$$ It is true for $j=2$: $m(2) = 5$, $f_5 = 5 = 1+2^2$ and $f_6 = 8 = 2^3$. Now $m(j+1) = 2 m(j) + 1$, so using the identity $f_{2m+1} = f_{m+1}^2 + f_{m}^2$ $$ f_{m(j+1)} = f_{m(j)+1}^2 + f_{m(j)}^2 \equiv 1 + 2^{j+1} \mod 2^{j+2}$$ because $f_{m(j)+1}^2$ is divisible by $2^{2(j+1)}$ and therefore by $2^{j+2}$, while if $x \equiv 1 + 2^j \mod 2^{j+1}$ with $j \ge 2$, $x^2 \equiv 1 + 2^{j+1} \mod 2^{j+2}$ Similarly, using the identity $f_{2m+2} = (2 f_m + f_{m+1}) f_{m+1}$, we get $$ f_{m(j+1)+1} = (2 f_{m(j)} + f_{m(j)+1}) f_{m(j)+1} \equiv 0 \mod 2^{j+2}$$ because the first factor is even and the second is divisible by $2^{j+1}$. By induction, the claim is proved.

One consequence of this is that $f_k \mod 2^j$ is periodic with period $m(j)+1$.

Next, I claim that if $f_k \equiv 1 \mod 2^j$ (with $j\ge 2$) then $k \equiv 1, 2$ or $-1 \mod m(j)+1$. Again we induct on $j$. It is true for $j=2$. Suppose it's true for $j$. If $f_k \equiv 1 \mod 2^{j+1}$ then $f_k \equiv 1 \mod 2^j$ so by the induction hypothesis $k \equiv 1, 2$ or $-1 \mod m(j)+1$, and thus (since $m(j+1)+1 = 2 (m(j)+1)$) $k \equiv 1, 2, m(j), m(j)+2, m(j)+3$ or $-1 \mod m(j+1)+1$. But by the above we know that $f_{m(j)} \equiv 1 + 2^j \mod 2^{j+1}$, and also both $f_{m(j)+2} = f_{m(j)} + f_{m(j)+1}$ and $f_{m(j)+3} = f_{m(j)+1} + f_{m(j)+2} \equiv 1 + 2^j \mod 2^{j+1}$. By the periodicity, $f_k \equiv 1 + 2^j \mod 2^{j+1}$ for $k \equiv m(j), m(j)+2$ or $m(j)+3 \mod m(j+1)+1$.
So that leaves only $1, 2$ and $-1 \mod m(j+1)+1$. This proves the claim.

In particular, there are no $k$ with $2 < k < m(j)$ such that $f_k \equiv 1 \mod 2^j$. And since $f_{m(j)} > m(j) > 2^j + 1$, this shows that $2^j + 1$ is not a Fibonacci number for $j > 2$.

share|improve this answer
    
Another great answer by Robert :) –  mick Oct 30 '12 at 19:40
    
A first question: (probably it won't be the last...) How can you see that $f_k\mod2^j$ is periodic with period $m(j)+1$? Of course it is periodic, but I don't know why it is with this period. –  barto Oct 30 '12 at 22:35
    
I think I almost know why. Since $f_{m(j)}\equiv1\pmod{2^j}$ and $f_{m(j)}\equiv0\pmod{2^j}$ we have that $f_{m(j)+x+1}\equiv f_x\pmod{2^j}$, and so the period is a divisor of $m(j)+1$. –  barto Oct 30 '12 at 22:51
    
The fact that the period is not smaller then $m(j)+1$ follows out of the fact that there are no $k$ with $2< k< m(j)$ such that $f_k\equiv1\pmod{2^j}$, right? If yes, then I finally understand your proof completely :) It is indeed awesome. –  barto Oct 31 '12 at 11:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.