Putnam 2020, Problem A-5

Let \( a_n \) be the number of sets \( S \) of positive integers for which
\[
\sum_{k \in S} F_k = n,
\]
where the Fibonacci sequence \( (F_k)_{k \geq 1} \) satisfies \( F_{k+2} = F_{k+1} + F_k \) and begins \( F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3 \). Find the largest integer \( n \) such that \( a_n = 2020 \).

Solution:
The answer is $n = F_{4040} - 1$. In both solutions, we use freely the identity
$$F_1 + F_2 + \cdots + F_{m-2} = F_m - 1 \tag{1}$$

which follows by a straightforward induction on $m$. We also use the directly computed values
$$a_1 = a_2 = 2, a_3 = a_4 = 3. \tag{2}$$

**First solution.** (by George Gilbert)
We extend the definition of $a_n$ by setting $a_0 = 1$.

**Lemma 1.** For $m > 0$ and $F_m \leq n < F_{m+1}$,
$$a_n = a_{n-F_m} + a_{F_{m+1}-n-1}. \tag{3}$$

*Proof.* Consider a set $S$ for which $\sum_{k \in S} F_k = n$. If $m \in S$ then $S \setminus \{m\}$ gives a representation of $n - F_m$, and this construction is reversible because $n - F_m < F_{m-1} \leq F_m$. If $m \notin S$, then $\{1,\ldots,m-1\} \setminus S$ gives a representation of $F_{m+1} - n - 1$, and this construction is also reversible. This implies the desired equality. $\square$

**Lemma 2.** For $m \geq 2$,
$$a_{F_m} = a_{F_{m+1}-1} = \left\lfloor \frac{m+2}{2} \right\rfloor. \tag{4}$$

*Proof.* By (2), this holds for $m = 2,3,4$. We now proceed by induction; for $m \geq 5$, given all preceding cases, we have by Lemma 1 that
$$a_{F_m} = a_0 + a_{F_{m-1}-1} = 1 + \left\lfloor \frac{m-1+2}{2} \right\rfloor = \left\lfloor \frac{m+2}{2} \right\rfloor$$
$$a_{F_{m+1}-1} = a_{F_{m-1}-1} + a_0 = a_{F_m}.$$

Using Lemma 2, we see that $a_n = 2020$ for $n = F_{4040} - 1$.

**Lemma 3.** For $F_m \leq n < F_{m+1}$, $a_n \geq a_{F_m}$.

*Proof.* We again induct on $m$. By Lemma 2, we may assume that
$$1 \leq n - F_m \leq (F_{m+1} - 2) - F_m = F_{m-1} - 2. \tag{5}$$

By (2), we may also assume $n \geq 6$, so that $m \geq 5$. We apply Lemma 1, keeping in mind that
$$(n - F_m) + (F_{m+1} - n - 1) = F_{m-1} - 1.$$

If $\max\{n - F_m, F_{m+1} - n - 1\} \geq F_{m-2}$ (by the induction hypothesis) and the other is at least $2$ (by (4) and the induction hypothesis), so
$$a_n \geq a_{F_{m-2}} + 2 = \left\lfloor \frac{m-2+2}{2} \right\rfloor + 2 = \left\lfloor \frac{m+4}{2} \right\rfloor.$$

Otherwise, $\min\{n - F_m, F_{m+1} - n - 1\} \geq F_{m-3}$ and so by the induction hypothesis again,
$$a_n \geq 2a_{F_{m-3}} = 2 \left\lfloor \frac{m-3+2}{2} \right\rfloor \geq 2 \left\lfloor \frac{m-2}{2} \right\rfloor \geq \left\lfloor \frac{m+2}{2} \right\rfloor. \square$$

Combining Lemma 2 and Lemma 3, we deduce that for $n > F_{4040} - 1$, we have $a_n \geq a_{F_{4040}} = 2021$. This completes the proof.

**Second solution.** We again start with a computation of some special values of $a_n$.

**Lemma 1.** For all $m \geq 1$,
$$a_{F_m-1} = \left\lfloor \frac{m+1}{2} \right\rfloor. \tag{6}$$

*Proof.* We proceed by induction on $m$. The result holds for $m = 1$ and $m = 2$ by (2). For $m > 2$, among the sets $S$ counted by $a_{F_m-1}$, by (1) the only one not containing $m - 1$ is $S = \{1,2,\ldots,m-2\}$, and there are $a_{F_m-F_{m-1}-1}$ others. Therefore,
$$a_{F_m-1} = a_{F_m-F_{m-1}-1} + 1$$
$$= a_{F_{m-2}-1} + 1 = \left\lfloor \frac{m-1+1}{2} \right\rfloor + 1 = \left\lfloor \frac{m+1}{2} \right\rfloor. \square$$

Given an arbitrary positive integer $n$, define the set $S_0$ as follows: start with the largest $k_1$ for which $F_{k_1} \leq n$, then add the largest $k_2$ for which $F_{k_1} + F_{k_2} \leq n$, and so on, stopping once $\sum_{k \in S_0} F_k = n$. Then form the bitstring
$$s_n = \cdots e_1 e_0, \quad e_k = \begin{cases} 1 & \text{if } k \in S_0 \\ 0 & \text{if } k \notin S_0 \end{cases}$$

note that no two 1s in this string are consecutive. We can thus divide $s_n$ into segments
$$t_{k_1,\ell_1} \cdots t_{k_r,\ell_r} \quad (k_i,\ell_i \geq 1)$$

where the bitstring $t_{k,\ell}$ is given by
$$t_{k,\ell} = (10)^k (0)^\ell$$

(that is, $k$ repetitions of 10 followed by $\ell$ repetitions of 0). Note that $\ell_r \geq 1$ because $e_1 = e_0 = 0$.

For $a = 1,\ldots,k$ and $b = 0,\ldots,\lfloor (\ell-1)/2 \rfloor$, we can replace $t_{k,\ell}$ with the string of the same length
$$(10)^{k-a} (0)(1)^{2a-1} (01)^b 10^{\ell-2b}$$

to obtain a new bitstring corresponding to a set $S$ with $\sum_{k \in S} F_k = n$. Consequently,
$$a_n \geq \prod_{i=1}^r \left(1 + k_i \left\lfloor \frac{\ell_i+1}{2} \right\rfloor \right). \tag{7}$$

For integers $k,\ell \geq 1$, we have
$$1 + k \left\lfloor \frac{\ell+1}{2} \right\rfloor \geq k + \left\lfloor \frac{\ell+1}{2} \right\rfloor \geq 2.$$

Combining this with repeated use of the inequality
$$xy \geq x + y \quad (x,y \geq 2),$$

we deduce that
$$a_n \geq \sum_{i=1}^r \left(k_i + \left\lfloor \frac{\ell_i+1}{2} \right\rfloor \right) \geq \left\lfloor 1 + \sum_{i=1}^r \frac{2k_i + \ell_i}{2} \right\rfloor.$$

In particular, for any even $m \geq 2$, we have $a_n > m/2$ for all $n \geq F_m$. Taking $m = 4040$ yields the desired result.

**Remark.** It can be shown with a bit more work that the set $S_0$ gives the unique representation of $n$ as a sum of distinct Virahanka-Fibonacci numbers, no two consecutive; this is commonly called the Zeckendorf representation of $n$, but was first described by Lekkerkerker. Using this property, one can show that the lower bound in (7) is sharp.