I gave an exam today that had a question which goes like-
a. We will call a binary sequence 'sparse' if there are no two consecutive $1$'s in it. Calculate number of sparse strings of length
$n$.b. Prove that every integer can be expressed as the sum of non-consecutive distinct Fibonacci numbers.
c. Prove that the sum in (b) is unique.
d. Either derive (a) using (b) and (c) or derive (c) using (a) and (b).
Now, I know very well how to find the recurrence relation in (a). I also studied the proofs of (b) and (c) a couple of years back, and didn't have much difficulty in constructing them from memory.
But, I got stuck in (d). I was trying to understand how to connect the results of (a), (b) and (c). After giving it a thought, I came up with this expression
\begin{equation*}
S(x_1,x_2,\dots ,x_n)=x_1F_1+x_2F_2+\dots +x_nF_n
\end{equation*}
for a given $k$ where $F_n$ is the largest Fibonacci number before $k$ and $x_i\in \{0,1\}\;\forall i\in\{1,2,\dots ,n\}$. Now, if we want $S=k$, then the sequence $x_1,x_2,\dots ,x_n$ must be sparse. But, from (a), we know that there are only $F_{n+2}$ such sparse sequences. Also, by (b), there exists a choice $(y_1,y_2,\dots ,y_n)=(x_1,x_2,\dots ,x_n)$ with $y_i\in \{0,1\}\;\forall i\in\{1,2,\dots ,n\}$ such that $S(y_1,y_2,\dots ,y_n)=k$. Also, it is clear that the values of $S$ that we can get by changing the choices of $x_i$'s are arranged in a strict order (i.e., any two of them cannot be equal). So, there is exactly one choice of $x_i$'s such that $S=k$.
But, there seems to be something fishy about my proof. I have not used the fact that there are $F_{n+1}$ choices of $x_i$'s anywhere in here. So, is my proof correct? If not, then is my approach correct? Can anybody please help me with this?
Best Answer
The maximum number that can be represented with a sparse sequence of length $n$ is $u_n=F_{n+1}+F_{n-1}+F_{n-3}+\dots$, where the sum stops at most at $F_2$ [1]. You can prove that $u_n=F_{n+2}-1$.
Now, if you can represent all numbers uniquely, between $0$ and $F_{n+2}-1$, that's $F_{n+2}$ numbers, which is precisely the number of sparse sequences of length $n$.
[1] As pointed out by arbashn above, the Fibonacci numbers that are used for the Zeckendorf represenation start at $F_2=1$.