$F_n$
for $n > 0$
by $F_n = F_{n1} + F_{n2}$
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?$

 What is the recursive formula for the sequence
$1, 7, 13, 19, 25, ...?$
 Find a nonrecursive formula for
$f(n)=2 \cdot f(n1)$
where$f(1) = 3.$
 What is the recursive formula for the sequence

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_{n1}$
are$0?$
Try proving your hypothesis by induction. 
Can you find a recursive definition of the answer?

When converting the recursive definition into a nonrecursive 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_{n1}$
because the sum of all Fibonacci numbers less than$F_{n1}$
will be less than than$F_n.$
Writing this mathematically, we get$\sum_{i=1}^{n2} 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_{n1} + F_n,$
where we can use our induction hypothesis for$F_n$
and see that$F_{n+1} > F_{n1} + \sum_{i=1}^{n2} F_i.$
Hence$\sum_{i=1}^{n1} 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_{n1} + F_{n2}.$
We can only write the first expression in one way. We cannot rewrite$F_{n1}$
due to the lemma above. Nonetheless, we can rewrite the second expression in$c_{n2}$
ways using the$c_{n2}$
ways to sum to$F_{n2}$
. This gives us the recursive definition$c_n=c_{n2}+1.$
We unwind the recursion to get$c_n=\lceil\frac{n+1}{2}\rceil.$