3. Define a sequence of integers as follows: $a_{1}=1, a_{2}=2$, and for $k \in \mathbb{N}, a_{k+2}=a_{k+1}+a_{k}$. How many different ways are there to write 2017 as a sum of distinct elements of this sequence?
3. Define a sequence of integers as follows: $a_{1}=1, a_{2}=2$, and for $k \in \mathbb{N}, a_{k+2}=a_{k+1}+a_{k}$. How many different ways are there to write 2017 as a sum of distinct elements of this sequence?
Answer: 24
Solution: Note that these $a_{k} \mathrm{~s}$ are in fact the Fibonacci numbers. Denote by $f(n)$ the number of distinct ways to express a number as a sum of $a_{k} \mathrm{~s}$. Note that $2017=1597+377+34+8+1=$ $a_{15}+a_{12}+a_{8}+a_{5}+a_{1}$.
We prove the following lemma:
$$
a_{1}+a_{2}+\cdots+a_{k}=a_{k+2}-2
$$

This follows simply from induction. It is true for $k=1$; adding $a_{k+1}$ to both sides and using the fact that $a_{k+1}+a_{k+2}=a_{k+3}$ gives the result.

Now, denote by $f(n)$ the number of ways to express $n$ as a sum of distinct $a_{k} \mathrm{~s}$; we are looking for $f$ (2017). Now, note that any such sum must contain either 1597 or 987 . If the sum does not contain 1597 , it must certainly contain 987 ; otherwise, from the lemma, the sum would be at most $1+2+\cdots+610=1595$. Moreover, if the sum contains 987 (but not 1597), it must also contain 610 ; otherwise, it will be at most $987+(1+2+\cdots+377)=987+985=1972$.
Hence, $f(2017)=2 f(420)$.
By a similar argument, any sum of 420 must contain either 377 or 233 . However, this time, it is perfectly possible for this sum to contain 233 but not 144 , since $233+(1+2+3+\cdots+89)=$ $464>420$. We thus have two cases to deal with.
Case 1: If the sum contains 377, then we have to compute $f(43)$. Now, note that as in the argument from earlier, any sum adding up to 43 contains either 34 or $13+21$. Hence $f(43)=2 f(9)$. Repeating this argument, we get $f(9)=2 f(1)=2$. This gives us $f(43)=4$.
Case 2: The sum does not contain 377. In this case, the sum must contain 233 . We then have to compute $f$ (187). Any sum adding up to 187 must contain either 144 or 89 ; moreover, if it contains 89 , it must contain 55 as well. Hence, $f(187)=2 f(43)=8$ by our previous computation.
Thus, $f(420)=3 f(43)=12$, and $f(2017)=24$.