Summing Fibonacci Numbers

Number Theory Level 1

True or False ?

Every positive integer can be written as the sum of one or more distinct Fibonacci numbers.

Clarification

Two $1$ 's occur in the Fibonacci sequence, so you can use it no more than two times: $4=1+1+2$ . All other Fibonacci numbers can be only used no more than once.

True Cannot be determined (depends on currently unsolved conjectures) False

1 solution

Nick Turtle
May 17, 2018

Proof by Induction

One can easily show that the statement is true for any positive integer $i\le F_3=2$ . This will be our base case.

Now, suppose that the statement is true for any $j\le F_n$ . We will show that the statement is also true for any $F_n<k\le F_{n+1}$ .

Given this $k$ , compute $k-F_n$ . Now, this number will always be less than $F_{n}$ since $F_{n+1}<2\cdot F_n$ for all $n\ge 3$ . Therefore, there exists distinct Fibonacci numbers not including $F_n$ that sum up to $k-F_n$ .

Thus, every positive integer can be written as the sum of one or more distinct Fibonacci numbers.

Nice problem and solution. We can go even further with Zeckendorf's Theorem, which states that every integer can be expressed uniquely as the sum of one or more distinct Fibonacci numbers such that no two of the numbers in the sum are consecutive Fibonacci numbers.

Brian Charlesworth - 3 years ago

Summing Fibonacci Numbers

1 solution

0 pending reports