A pennant is a sequence of numbers, each number being 1 or 2. An $n$-pennant is a sequence of numbers with sum equal to $n$. For example, $(1,1,2)$ is a 4-pennant. The set of all possible 1-pennants is $\{(1)\}$, the set of all possible 2-pennants is $\{(2), (1,1)\}$and the set of all 3-pennants is $\{(2,1), (1,1,1), (1,2)\}$. Note that the pennant $(1,2)$ is not the same as the pennant $(2,1)$. The number of 10-pennants is ________.

Let $P(n)$ denote the number of $n$-pennants.

An $n$-pennant can start with either:

1. A $1$, followed by any $(n-1)$-pennant, which gives $P(n-1)$ possibilities.

2. A $2$, followed by any $(n-2)$-pennant, which gives $P(n-2)$ possibilities.

This yields the recurrence relation:

Given the base cases:

• $P(1) = 1$

• $P(2) = 2$

Computing the values successively:

• $P(3) = 1 + 2 = 3$

• $P(4) = 2 + 3 = 5$

• $P(5) = 3 + 5 = 8$

• $P(6) = 5 + 8 = 13$

• $P(7) = 8 + 13 = 21$

• $P(8) = 13 + 21 = 34$

• $P(9) = 21 + 34 = 55$

• $P(10) = 34 + 55 = 89$

Thus, the number of 10-pennants is 89.