Sum of Non-Consecutive Fibonacci Numbers

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a non-empty set of distinct non-consecutive Fibonacci numbers not containing $F_0$ or $F_1$.

Let the largest element of $S$ be $F_j$.

Then:

$\ds \sum_{F_i \mathop \in S} F_i < F_{j + 1}$

That is, the sum of all the elements of $S$ is strictly less than the next largest Fibonacci number.

That is, given some increasing sequence $\sequence {c_i}$ satisfying $c_i \ge 2$ and $c_{i + 1} \ge c_i + 1$:

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


Proof

The proof proceeds by induction on $j$ for $j \ge 2$.

For all $j \in \N_{>0}$, let $\map P j$ be the proposition:

$\ds \sum_{F_i \mathop \in S} F_i < F_{j + 1}$


Let the term allowable set be used to mean a non-empty set of distinct non-consecutive Fibonacci numbers not containing $F_0$ or $F_1$.


Basis for the Induction

The only possible allowable set whose largest member is $F_2 = 1$ is the set:

$\set {F_2} = \set 1$

This has sum $1$, which is strictly less than $F_3 = 2$.


This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.


So this is our induction hypothesis:

$\ds \sum_{F_i \mathop \in S} F_i < F_{k + 1}$

where $S$ is an allowable set whose largest element is $F_k$.

Then we need to show:

$\ds \sum_{F_i \mathop \in S} F_i < F_{k + 2}$

where $S$ is an allowable set whose largest element is $F_{k + 1}$.


Induction Step

This is our induction step:

Let $S$ be an allowable set whose greatest element is $F_{k + 1}$.

Let $S' := S \setminus \set {F_{k + 1} }$.

That is, $S'$ is $S$ without its largest element $F_{k + 1}$.

We have that $S$ cannot contain consecutive Fibonacci numbers.

Hence the largest element of $S'$ is at most $F_{k - 1}$.

So by the induction hypothesis:

$\ds \sum S' < F_k$

Then:

\(\ds \sum S\) \(=\) \(\ds \sum S' + F_{k + 1}\)
\(\ds \) \(<\) \(\ds F_k + F_{k + 1}\)
\(\ds \) \(<\) \(\ds F_{k + 2}\) Definition of Fibonacci Numbers

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\ds \forall j \in \N_{> 0}: \sum_{F_i \mathop \in S} F_i < F_{j + 1}$

$\blacksquare$

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_Non-Consecutive_Fibonacci_Numbers&oldid=600581"