The case $x=2$ is still tractable. If $F_n = 2^e + 2^f$ with $e<f$
then $e < 5$, else $F_n \equiv 0 \bmod 2^5$, which happens **iff**
$n \equiv 0 \bmod 24$, and then $7 \mid 21 = F_8 \mid F_{24} \mid F_n$,
which is impossible because $2^e + 2^f$ is never a multiple of $7$.
So we have only a few candidates for $e$, and we can deal with
each of them separately, possibly even by elementary means,
to show that $(n,e,f) = (12,4,7)$ is the last solution.

$\langle$ **EDIT** $\rangle$
Here's such an elementary proof.
For each $e$ (other than the trivial $e=2$), we choose some $f_0 > e$,
try each $f$ with $e < f_0 < f$, and then once $f \geq f_0$ we use
the condition $F_n = 2^e + 2^f \equiv 2^e \bmod 2^f$ to get a
congruence condition on $n$, and then reach a contradiction by considering
$F_n$ modulo some odd prime (usually $3$, but with one much larger exception).

$e=0$: We take $f_0 = 4$. Trying $f=1$ and $f=2$ yields
the Fibonacci numbers $F_4=3$ and $F_5=5$,
and $f=3$ yields the non-Fibonacci number $9$. Once $f \geq 4$
we have $F_n \equiv 1 \bmod 16$. But $F_n \bmod 16$ is periodic with
period $24$, and it turns out that the remainder is $1$ only for
$n \equiv 1, 2, 23 \bmod 24$. But $F_n \bmod 3$ has period $8$,
which is a factor of $24$; and $F_1 = F_2 = F_{-1} = 1$.
We deduce $F_n \equiv 1 \bmod 3$.
Hence $2^f \equiv 0 \bmod 3$, which is impossible.

$e=1$: The Fibonacci numbers $F_n$ congruent to $2 \bmod 4$
are those with $n \equiv 3 \bmod 6$, and these always turn out to be
$2 \bmod 32$. Thus $f \geq 5$, and $f=5$ yields the Fibonacci number
$34 = F_9$. We claim that this is the only possibility, using $f_0 = 6$.
Once $f \geq 6$ we have $F_n \equiv 2 \bmod 64$, and then
$n \equiv \pm 3 \bmod 24$. But (again thanks to $8$-periodicity mod $3$)
this implies $F_n \equiv 2 \bmod 3$, so once more we reach
a contradiction from the congruence $2^f \equiv 0 \bmod 3$.

$e=2$: impossible because $F_n$ is never $2 \bmod 4$.

$e=3$: We take $f_0=5$. Since $2^3 + 2^4 = 24$ is not a Fibonacci number,
we may assume $f \geq 5$, and then $F_n \equiv 8 \bmod 32$. This is
equivalent to $n \equiv 6 \bmod 24$, which again yields a contradiction
mod $3$ since $2^f = F_n - 2^e$ would have to be a multiple of $3$.

$e=4$: This is the hardest case:
because $f=7$ yields $144 = F_{12}$, it is not enough to use
congruences that can be deduced from $F_n \equiv 2 \bmod 2^7$,
and we must take $f_0 > 7$. It turns out that $f_0 = 9$ works.
Then $f=5,6,8$ yield the non-Fibonacci $48, 80, 272$.
Once $f \geq 9$ we must have $F_n \equiv 16 \bmod 2^9$.
Now $F_n \bmod 2^9$ has period $768$,
but the condition $F_n \equiv 16 \bmod 2^9$ determines $n \bmod 384$
(half of $768$), and we compute $n \equiv -84 \bmod 384$.
Now $n \bmod 384$ determines $F_n$ modulo the prime $4481$
(the period is $128$), and we find $F_n \equiv 2284 \bmod 4481$,
whence $2^f = F_n - 2^e \equiv 2284 - 16 = 2268 \bmod 4481$.
But this is impossible because $2$ is a fourth power (even an $8$th power)
mod $4481$, and $2268$ is not.

$\langle$ **/EDIT** $\rangle$

But I doubt that one can prove that such a technique can work for all $x$...

numberof solutions of $w(F_n) \leq x$ may be effectively bounded). – Noam D. Elkies Mar 2 '14 at 6:28