We define the Fibonnaci numbers $F_n$ for $n > 0$ by $F_n = F_{n-1} + F_{n-2}$ with $F_1 = F_2 = 1.$ In how many ways can $F_n$ be expressed in the form $\sum_{i=1}^{n} a_i F_i$ where each $a_i$ is either $0$ or $1?$
  1. What is the recursive formula for the sequence $1, 7, 13, 19, 25, ...?$
  2. Find a non-recursive formula for $f(n)=2 \cdot f(n-1)$ where $f(1) = 3.$

Consider the first few Fibonacci numbers. In how many ways of the desired form can they be expressed?

Are there any $F_k$ that one must use to express $F_n?$

Is it possible to express $F_n$ in the required form where the coefficients of $F_n$ and $F_{n-1}$ are $0?$ Try proving your hypothesis by induction.

Can you find a recursive definition of the answer?

When converting the recursive definition into a non-recursive form, it may be helpful to initially consider the odd and even terms separately.

In order to sum to $F_n$ without using $F_n$ itself, we must include $F_{n-1}$ because the sum of all Fibonacci numbers less than $F_{n-1}$ will be less than than $F_n.$ Writing this mathematically, we get $\sum_{i=1}^{n-2} F_i < F_n,$ which we can prove by induction. The base case, $n = 3,$ is clearly true since $F_1=1$ and $F_3 = 2.$ For the induction step, we start with $F_{n+1} = F_{n-1} + F_n,$ where we can use our induction hypothesis for $F_n$ and see that $F_{n+1} > F_{n-1} + \sum_{i=1}^{n-2} F_i.$ Hence $\sum_{i=1}^{n-1} F_i \lt F_{n+1},$ which completes our proof.

Let $c_i$ be the number of ways we can sum to $F_i.$ We have $c_1=1$ and $c_2=2.$ To sum to $F_n,$ we can have $F_n$ or $F_{n-1} + F_{n-2}.$ We can only write the first expression in one way. We cannot rewrite $F_{n-1}$ due to the lemma above. Nonetheless, we can rewrite the second expression in $c_{n-2}$ ways using the $c_{n-2}$ ways to sum to $F_{n-2}$. This gives us the recursive definition $c_n=c_{n-2}+1.$ We unwind the recursion to get $c_n=\lceil\frac{n+1}{2}\rceil.$