$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?$
-
- What is the recursive formula for the sequence
$1, 7, 13, 19, 25, ...?$ - Find a non-recursive formula for
$f(n)=2 \cdot f(n-1)$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_{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.$