SAUDI ARABIAN MATHEMATICAL COMPETITIONS

1. We will prove by induction that every positive integer $k$ can be written as sum of several distinct Fibonacci numbers. The case $k=1$ is obvious, we have $1=f_1$. Assume that every positive integer less than $n$ can be written as sum of several distinct Fibonacci numbers, consider $k=n$. We can find $f_i$ is the greatest Fibonacci number which is less than $n$, we have $$n=f_i+\left(n-f_i\right).$$ According to the induction hypothesis, $n-f_i$ is a positive integer less than $n$, therefore it can be written as $$n-f_i=f_{j_1}+f_{j_2}+\cdots +f_{j_t},j_1<j_2<\dots <j_t.$$ We must have $i>j_t$ because otherwise, $n=f_i+f_{j_t}+\cdots >f_i+f_{i-1}=f_{i+1}$, contradiction to the choice of $i$. So, $n=f_{j_1}+f_{j_2}+\cdots +f_{j_t}+f_i$, which is a representation of $n$ as sum of distinct Fibonacci numbers, we are done.

2. According to the part 1., an integer $n$ can be written as $$n=f_{i_1}+f_{i_2}+\cdots +f_{i_k},i_1<i_2<\cdots <i_k.$$ We need to find all $n$ of which representation is unique. First, if $i_1\ge 3$, then we can replace $f_{i_1}$ by $f_{i_1-1}+f_{i_1-2}$ and get another representation of $n$. So if $n$ is a "Fib-unique", $i_1\in \{1,2\}$. Second, if there is some $t$ such that $i_{t+1}-i_t\ge 3$, then we can replace $f_{i_{t+1}}$ by $f_{i_{t+1}-1}+f_{i_{t+1}-2}$ and get another representation of $n$. Hence, for a "Fib-unique" integer $n$, we have $i_{t+1}-i_t\le 2$ for every $0\le t\le k-1$. Third, if we have some $t$ such that $i_{t+1}-i_t=1$, chose that $t$ which is the largest. Then we can replace $f_{i_{t+1}}+f_{i_t}$ by $f_{i_{t+1}+1}$, and get another representation of $n$. So for a "fib-unique" $n$ we must have $i_{t+1}-i_t=2$ for every $0\le t\le k-1$. So, every possible "Fib-unique" positive $n$ are $f_1,f_2$ and those in these forms: $$\begin{array}{rl}& \text{ i . }n=f_1+f_3+\cdots +f_{2k-1}=f_{2k}-1\\ & \text{ ii . }n=f_2+f_4+\cdots +f_{2k}=f_{2k+1}-1\end{array}$$ In conclusion, every Fib-unique is $f_1,f_2$ and $f_k-1$ with $k\ge 3$. $\square$