Smallest Positive Integer with 5 Fibonacci Partitions

From ProofWiki
Jump to navigation Jump to search

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