Advent calendar 2024
3 December
There are 5 ways to write 5 as the sum of positive odd numbers:
- 1 + 1 + 1 + 1 + 1
- 1 + 1 + 3
- 3 + 1 + 1
- 1 + 3 + 1
- 5
How many ways are there to write 14 as the sum of positive odd numbers?
Show answer
Hide answer
This can be solved by working it out for some examples then looking for the pattern:
| Total | Ways to make | Number of ways |
| 1 | 1 | 1 |
| 2 | 1+1 | 1 |
| 3 | 1+1+1, 3 | 2 |
| 4 | 1+1+1+1, 3+1, 1+3 | 3 |
| 5 | 1+1+1+1+1, 1+1+3, 1+3+1, 3+1+1 | 5 |
| 6 | 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 3+1+1+1, 3+3, 5+1, 1+5 | 8 |
The looks like the Fibonacci numbers: every term is the sum of the previous two terms.
Continuing the pattern gives 377 ways to make 14.
To justify why the answer is the Fibonacci numbers, notice that you split the sums for a number n into two sets:
those that end with "+1" and those that end with something else.
Those that end with "+1" are a way of making n-1, plus the one on the end.
Those that don't end with "+1" are a way of making n-2, with two added to the final number.
So the number of ways of making n is
the number of ways of making n-1 plus the number of ways of making n-2.
