Advent calendar 2018
1 December
There are 5 ways to write 4 as the sum of 1s and 2s:
- 1+1+1+1
- 2+1+1
- 1+2+1
- 1+1+2
- 2+2
Today's number is the number of ways you can write 12 as the sum of 1s and 2s.
Show answer
Hide answer
233
Let \(f(n)\) be the number of ways to write \(n\) as the sum of 1s and 2s.
When you write \(n\) as the sum of 1s and 2s, the sum must end in either 1 or 2: if it ends in 1, then there are \(f(n-1)\) ways to write the
rest before this 1 as the sum of 1s and 2s; if it ends in 2, there are \(f(n-2)\) ways to write the rest.
This means that \(f(n)=f(n-1)+f(n-2)\), or in other words the Fibonacci numbers.
