Smallest Positive Integer with 5 Fibonacci Partitions
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
\(\ds 1\) | \(=\) | \(\ds 1\) | $1$ way | |||||||||||
\(\ds 2\) | \(=\) | \(\ds 2\) | $1$ way | |||||||||||
\(\ds 3\) | \(=\) | \(\ds 3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 2 + 1\) | $2$ ways | |||||||||||
\(\ds 4\) | \(=\) | \(\ds 3 + 1\) | $1$ way | |||||||||||
\(\ds 5\) | \(=\) | \(\ds 5\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 3 + 2\) | $2$ ways | |||||||||||
\(\ds 6\) | \(=\) | \(\ds 5 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 3 + 2 + 1\) | $2$ ways | |||||||||||
\(\ds 7\) | \(=\) | \(\ds 5 + 2\) | $1$ way | |||||||||||
\(\ds 8\) | \(=\) | \(\ds 8\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 5 + 3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 5 + 2 + 1\) | $3$ ways | |||||||||||
\(\ds 9\) | \(=\) | \(\ds 8 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 5 + 3 + 1\) | $2$ ways | |||||||||||
\(\ds 10\) | \(=\) | \(\ds 8 + 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 5 + 3 + 2\) | $2$ ways | |||||||||||
\(\ds 11\) | \(=\) | \(\ds 8 + 3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 2 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 5 + 3 + 2 + 1\) | $3$ ways | |||||||||||
\(\ds 12\) | \(=\) | \(\ds 8 + 3 + 1\) | $1$ way | |||||||||||
\(\ds 13\) | \(=\) | \(\ds 13\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 5\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 3 + 2\) | $3$ ways | |||||||||||
\(\ds 14\) | \(=\) | \(\ds 13 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 5 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 3 + 2 + 1\) | $3$ ways | |||||||||||
\(\ds 15\) | \(=\) | \(\ds 13 + 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 5 + 2\) | $2$ ways | |||||||||||
\(\ds 16\) | \(=\) | \(\ds 13 + 3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 2 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 5 + 3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 5 + 2 + 1\) | $4$ ways | |||||||||||
\(\ds 17\) | \(=\) | \(\ds 13 + 3 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 5 + 3 + 1\) | $2$ ways | |||||||||||
\(\ds 18\) | \(=\) | \(\ds 13 + 5\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 3 + 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 5 + 3 + 2\) | $3$ ways | |||||||||||
\(\ds 19\) | \(=\) | \(\ds 13 + 5 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 3 + 2 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 8 + 5 + 3 + 2 + 1\) | $3$ ways | |||||||||||
\(\ds 20\) | \(=\) | \(\ds 13 + 5 + 2\) | $1$ way | |||||||||||
\(\ds 21\) | \(=\) | \(\ds 21\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 8\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 5 + 3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 5 + 2 + 1\) | $4$ ways | |||||||||||
\(\ds 22\) | \(=\) | \(\ds 21 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 8 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 5 + 3 + 1\) | $3$ ways | |||||||||||
\(\ds 23\) | \(=\) | \(\ds 21 + 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 8 + 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 5 + 3 + 2\) | $3$ ways | |||||||||||
\(\ds 24\) | \(=\) | \(\ds 21 + 3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 21 + 2 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 8 + 3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 13 + 8 + 2 + 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 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: pp. 289 – 306)
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $24$