Sum of Non-Consecutive Fibonacci Numbers

Theorem

The sum of any non-empty set of distinct, non-consecutive Fibonacci numbers not containing $F_0$ or $F_1$ whose largest member is $F_j$ is strictly less than the next largest Fibonacci number $F_{j + 1}$.

That is, given some increasing sequence $\left\langle{ c_i }\right\rangle$ satisfying $c_i \geq 2$ and $c_{i + 1} \geq c_i + 1$

$\displaystyle F_{c_k + 1} > \sum_{i = 0}^k F_{c_i}$.

Proof

We will use induction on $j$.

Base case ($j = 2$): Clearly the only possible non-empty set of distinct, non-consecutive Fibonacci numbers whose largest member is $F_2 = 1$ is the set $\left\{ F_2 \right\} = \left\{ 1 \right\}$. This has sum $1$, which is strictly less than $F_3 = 2$, so the base case holds.

Now assume the statement holds for $j \leq n$ and examine the case of $n + 1$.

Let's call our set of Fibonacci numbers $S$. We define $S' = S \setminus \left\{ F_{n + 1} \right\}$, that is, $S$ without its largest element $F_{n + 1}$.

The largest element of $S'$ is at most $F_{n - 1}$ since $S$ cannot contain consecutive Fibonacci Numbers, so by the inductive hypothesis, the sum of $S'$ is strictly less than $F_n$.

But then the sum of $S$ (i.e. the sum of $S'$ plus $F_{n + 1}$) is strictly less than $F_n + F_{n + 1} = F_{n + 2}$, which is exactly what we wanted to show.

$\blacksquare$