Question 59

Let $P(n)$ be the number of $n$-pennants (ordered sequences of 1s and 2s that sum to $n$).

Consider the last number in an $n$-pennant:

• If the last number is 1, the preceding sequence must sum to $n - 1$, which is an $(n-1)$-pennant. There are $P(n-1)$ such pennants.
• If the last number is 2, the preceding sequence must sum to $n - 2$, which is an $(n-2)$-pennant. There are $P(n-2)$ such pennants.

Therefore, $P(n)$ satisfies the Fibonacci recurrence:

Given initial conditions:

• $P(1) = 1$ (sequence: (1))
• $P(2) = 2$ (sequences: (2), (1, 1))
• $P(3) = 3$ (sequences: (2, 1), (1, 1, 1), (1, 2))

Computing subsequent values:

• $P(4) = P(3) + P(2) = 3 + 2 = 5$
• $P(5) = P(4) + P(3) = 5 + 3 = 8$
• $P(6) = P(5) + P(4) = 8 + 5 = 13$
• $P(7) = P(6) + P(5) = 13 + 8 = 21$
• $P(8) = P(7) + P(6) = 21 + 13 = 34$
• $P(9) = P(8) + P(7) = 34 + 21 = 55$
• $P(10) = P(9) + P(8) = 55 + 34 = 89$

Thus, the number of 10-pennants is 89.