Mathematical Reflections 2013, Issue 1 - Problem J254

Problem:
Solve the following equation $F_{a_1} + F_{a_2} + \ldots + F_{a_k} = F_{a_1+a_2+\ldots+a_k}$ , where $F_i$ is the $i$-th
Fibonacci number.

Proposed by Roberto Bosch Cabrera.

Solution:
If $k=1$ the equation has infinitely many solutions. Let $k \geq 2$ and suppose that $1 \leq a_1 \leq a_2 \leq \ldots \leq a_k$.
We have five cases.

(i) $k=2$. Suppose that $a_1+a_2 \leq 4$. It's easy to see that $(1,2)$ and $(1,3)$ are solutions. Now, suppose that $a_1+a_2 \geq 5$. If $a_1=1$, then $a_2 \geq 4$ and $F_{a_1+a_2-2}>F_{a_1}$. If $a_1>1$, then $a_2>2$, so $F_{a_1+a_2-1}>F_{a_2}$ and $$F_{a_1+a_2}=F_{a_1+a_2-1}+F_{a_1+a_2-2} > F_{a_2}+F_{a_1},$$ i.e. the equation has no solution if $a_1+a_2 \geq 5$.

(ii) $k=3$. There are no solutions when $a_3=1$. If $a_3=2$, we have the solution $(1,1,2)$. It's easy to see that there are no more solutions such that $a_2=1$ and $a_3>2$. Suppose that $a_3 \geq 2$ and $a_2 \geq 2$. If $a_3=2$, we get $F_{a_1+a_2+a_3-1}>F_{a_3}$ and if $a_3>2$, we get $F_{a_1+a_2+a_3-2}>F_{a_1+a_2}$, so $$F_{a_1+a_2+a_3}=F_{a_1+a_2+a_3-1}+F_{a_1+a_2+a_3-2}>F_{a_3}+F_{a_1+a_2} \geq F_{a_3}+F_{a_2}+F_{a_1},$$ i.e. no solution if $a_3>2$.

(iii) $k=4$. A simple check shows that there are no solutions if $a_4=1$. If $a_4 \geq 2$ and $a_3=1$ there are no solutions, and if $a_3 \geq 2$, we can argue similarly to the previous case and conclude that $$F_{a_1+a_2+a_3+a_4} > F_{a_4}+F_{a_1+a_2+a_3} \geq F_{a_4}+F_{a_3}+F_{a_2}+F_{a_1},$$ i.e. no solution in this case.

(iv) $k=5$. If $a_5=1$, we immediately see that $(1,1,1,1,1)$ is a solution. If $a_5 \geq 2$ and $a_4=1$, there are no solutions and if $a_4 \geq 2$ we get $$F_{a_1+a_2+a_3+a_4+a_5}>F_{a_5}+F_{a_1+a_2+a_3+a_4}\geq F_{a_5}+F_{a_4}+F_{a_3}+F_{a_2}+F_{a_1}.$$

(v) $k>5$. Clearly, $a_1+a_2+\ldots+a_k \geq k$. If $a_k=1$, there are no solutions since $a_1+a_2+\ldots+a_k=k$ and $F_k>k$. If $a_k \geq 2$ and $a_{k-1}=1$, then $a_1+a_2+\ldots+a_{k-1}=k-1$ and
$$\begin{array}{lcl} F_{a_1+a_2+\ldots+a_k}&=&F_{a_1+a_2+\ldots+a_k-1}+F_{a_1+a_2+\ldots+a_k-2}\\&>&F_{a_k}+F_{a_1+a_2+\ldots+a_{k-1}} =  F_{a_k}+F_{k-1} \\ & \geq & F_{a_k}+k-1 \\ & = & F_{a_k}+F_{a_{k-1}}+\ldots+F_{a_1}. \end{array}$$
If $a_k \geq 2$ and $a_{k-1} \geq 2$, we have
$$\begin{array}{lcl} F_{a_1+a_2+\ldots+a_k} & > & F_{a_k}+ F_{a_1+a_2+\ldots+a_{k-1}}\\ & > & F_{a_k}+F_{a_{k-1}} + F_{a_1+a_2+\ldots+a_{k-2}} \\ & \geq & F_{a_k}+F_{a_{k-1}}+F_{a_{k-2}}+F_{a_1+a_2+\ldots+a_{k-3}} \\ & \vdots & \vdots \\ & \geq & F_{a_k}+F_{a_{k-1}}+\ldots+F_{a_2}+F_{a_1}-1 , \end{array}$$ which gives $F_{a_1+a_2+\ldots+a_k} > F_{a_k}+F_{a_{k-1}}+\ldots+F_{a_2}+F_{a_1}$, so there are no solutions in this case.