Every year, legend Matt Scroggs runs an advent calendar of puzzles, with a prize for some lucky winners. I have enough Chalkdust T-shirts to suggest that I must have won at least once. There is always at least one nice, chewy problem; this year, it was on day 3:

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?

There will, of course, be spoilers below the line; the deadline for prizes has, of course, passed.

Scroggs mentioned (probably in the Finite Group Discord) that he hadn’t calibrated the difficulty right for a puzzle so early in the month. It is definitely a puzzle where finding the answer isn’t too hard, but finding the solution requires looking at it from the correct angle.

Finding an answer

There is/are:

  • One way to create 1.
  • One way to create 2 ($1+1$).
  • Two ways to create 3 ($3$ and $1+1+1$)
  • Three ways to create 4 ($3+1$, $1+3$ and $1+1+1+1$)
  • Five ways to create 5 (as we’ve seen)

That’s a fairly well-known sequence, and it’s the work of a moment on Wolfram|Alpha to determine that there are $F_{14} = 377$ ways to create 14.

Yes, but WHY?

I spent insufferably long looking for ways to shoehorn the permutations into the diagonals of Pascal’s triangle, an approach I now believe to be doomed. My eventual solution is much simpler.

Let’s look at 6 – we hypothesise that there are eight ways to make it. We can do it by:

  • Prepending a $1$ to the solutions for 5 (five ways)
  • Prepending a $3$ to the solutions for 3 (two ways)
  • Prepending a $5$ to the solutions for 1 (one way)

Amazing! Only… that’s not the way the Fibonacci sequence is usually built up, is it? It’s usually the previous two terms added together.

Luckily, our friend proof by induction comes to the rescue! I’m only going to give a sketch here. I want to show that $F_{2n} = \sum_{r=1}^{n} F_{2r-1}$ – so for $n=3$, that would be $F_6 = F_1 + F_3 + F_5$ as we worked out above.

The base case for $F_2$ is trivially true. Now suppose it holds for $n=k$ and consider $n = k+1$ – that is, I’m interested in $F_{2k + 2}$. By definition, that’s $F_{2k+1} + F_{2k}$, and by supposition $F_{2k} = \sum_{r=1}^{n} F_{2r-1}$, so $F_{2k+2} = F_{2k+1} + F_{2k-1} + F_{2k-3} + \dots$.

Writing out the details is left as an exercise.

I found that to be an interesting Fibonacci fact I hadn’t come across before. Did you approach it a different way? I’d love to hear about it.

  • Edited 2025-01-11 to fix markdown.