Smallest Positive Integer with 5 Fibonacci Partitions

Theorem

The smallest positive integer which can be partitioned into distinct Fibonacci numbers in $5$ different ways is $24$.

Proof

\(\displaystyle 1\)

\(=\)

\(\displaystyle 1\)

$1$ way

\(\displaystyle 2\)

\(=\)

\(\displaystyle 2\)

$1$ way

\(\displaystyle 3\)

\(=\)

\(\displaystyle 3\)

\(\displaystyle \)

\(=\)

\(\displaystyle 2 + 1\)

$2$ ways

\(\displaystyle 4\)

\(=\)

\(\displaystyle 3 + 1\)

$1$ way

\(\displaystyle 5\)

\(=\)

\(\displaystyle 5\)

\(\displaystyle \)

\(=\)

\(\displaystyle 3 + 2\)

$2$ ways

\(\displaystyle 6\)

\(=\)

\(\displaystyle 5 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 3 + 2 + 1\)

$2$ ways

\(\displaystyle 7\)

\(=\)

\(\displaystyle 5 + 2\)

$1$ way

\(\displaystyle 8\)

\(=\)

\(\displaystyle 8\)

\(\displaystyle \)

\(=\)

\(\displaystyle 5 + 3\)

\(\displaystyle \)

\(=\)

\(\displaystyle 5 + 2 + 1\)

$3$ ways

\(\displaystyle 9\)

\(=\)

\(\displaystyle 8 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 5 + 3 + 1\)

$2$ ways

\(\displaystyle 10\)

\(=\)

\(\displaystyle 8 + 2\)

\(\displaystyle \)

\(=\)

\(\displaystyle 5 + 3 + 2\)

$2$ ways

\(\displaystyle 11\)

\(=\)

\(\displaystyle 8 + 3\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 2 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 5 + 3 + 2 + 1\)

$3$ ways

\(\displaystyle 12\)

\(=\)

\(\displaystyle 8 + 3 + 1\)

$1$ way

\(\displaystyle 13\)

\(=\)

\(\displaystyle 13\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 5\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 3 + 2\)

$3$ ways

\(\displaystyle 14\)

\(=\)

\(\displaystyle 13 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 5 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 3 + 2 + 1\)

$3$ ways

\(\displaystyle 15\)

\(=\)

\(\displaystyle 13 + 2\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 5 + 2\)

$2$ ways

\(\displaystyle 16\)

\(=\)

\(\displaystyle 13 + 3\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 2 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 5 + 3\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 5 + 2 + 1\)

$4$ ways

\(\displaystyle 17\)

\(=\)

\(\displaystyle 13 + 3 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 5 + 3 + 1\)

$2$ ways

\(\displaystyle 18\)

\(=\)

\(\displaystyle 13 + 5\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 3 + 2\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 5 + 3 + 2\)

$3$ ways

\(\displaystyle 19\)

\(=\)

\(\displaystyle 13 + 5 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 3 + 2 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 8 + 5 + 3 + 2 + 1\)

$3$ ways

\(\displaystyle 20\)

\(=\)

\(\displaystyle 13 + 5 + 2\)

$1$ way

\(\displaystyle 21\)

\(=\)

\(\displaystyle 21\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 8\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 5 + 3\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 5 + 2 + 1\)

$4$ ways

\(\displaystyle 22\)

\(=\)

\(\displaystyle 21 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 8 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 5 + 3 + 1\)

$3$ ways

\(\displaystyle 23\)

\(=\)

\(\displaystyle 21 + 2\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 8 + 2\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 5 + 3 + 2\)

$3$ ways

\(\displaystyle 24\)

\(=\)

\(\displaystyle 21 + 3\)

\(\displaystyle \)

\(=\)

\(\displaystyle 21 + 2 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 8 + 3\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 8 + 2 + 1\)

\(\displaystyle \)

\(=\)

\(\displaystyle 13 + 5 + 3 + 2 + 1\)

$5$ ways

This sequence is A000119 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

$\blacksquare$

Sources

• 1966: David A. Klarner: Representations of $n$ as a Sum of Distinct Elements from Special Sequences (The Fibonacci Quarterly Vol. 4: 289 – 306)

• 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $24$