Fibonacci sequences is defined as $f_1=1$,$f_2=2$, $f_{n+1}=f_{n}+f_{n-1}$ for $n \ge 2$. a) Prove that every positive integer can be represented as sum of several distinct Fibonacci number. b) A positive integer is called Fib-unique if the way to represent it as sum of several distinct Fibonacci number is unique. Example: $13$ is not Fib-unique because $13 = 13 = 8 + 5 = 8 + 3 + 2$. Find all Fib-unique.
Problem
Source: 2017 Saudi Arabia BMO TST I p4
Tags: fibonacci number, number theory
03.08.2020 08:05
This can be easily solved by strong induction. (a). The base case, $k=1$ is trivial. Assume that for all $k\leq j$, the given statement is true. Then for $k=j+1$, if $j+1$ is a Fibonacci number, then we are done. If not, then there exists $f_{n},f{n+1}$ such that \[f_{n}<j+1<f_{n+1}\]for some $n$. Observe that $j+1-f_{n}<j$ so we have \[j+1-f_{n}=f_{\alpha_1}+f_{\alpha_2}+\ldots +f_{\alpha_i}\]where $\alpha_1,\alpha_2, \ldots \alpha_i\geq 1$ and they are distinct by our inductive hypothesis. Also all the terms $f_{\alpha_i}\ne f_{n}$ since $j+1-f_{n}<f_{n+1}-f_{n}=f_{n-1}<f_{n}$. Thus, we have \[j+1=f_{n}+f_{\alpha_1}+f_{\alpha_2}+\ldots +f_{\alpha_i}\]which completes our inductive step. (b). The answer is all $n\in \mathbb{N}$ and $n$ is not a Fibonacci number, except for $n=1$. Indeed if $n$ is a Fibonacci number and isn't $1$, then it is equal to itself and sum of two Fibonacci numbers which means it is not a Fib-unique. It is easy to see that $1$ is a Fib-unique. Now, consider the set of positive integers that are not Fibonacci numbers, let $n_1,n_2,\ldots$ be the elements of this set and $n_1=4$. We show that they can be written uniquely as the sum of distinct and non-consecutive Fibonacci numbers. Then base case $n=4$ can only be written as $1+3$. Then, we use strong induction again as in (a) by assuming that for all $n_i\leq n_k$ works where $i\leq k$ and consider $n_{k+1}$.