A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is…
2014
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 ______________.
Attempted by 22 students.
Show answer & explanation
Correct answer: 88.9 to 89.1
Key idea: Count sequences by their first term.
Let a_n be the number of n-pennants (sequences of 1s and 2s summing to n).
Recurrence: a_n = a_{n-1} + a_{n-2}.
Reason: any n-pennant either starts with 1 (then the rest is an (n-1)-pennant) or starts with 2 (then the rest is an (n-2)-pennant), and these cases are disjoint.
Base cases:
a_1 = 1 (only the sequence (1)).
a_2 = 2 (the sequences (2) and (1,1)).
Compute iteratively up to n = 10:
a_1 = 1
a_2 = 2
a_3 = a_2 + a_1 = 2 + 1 = 3
a_4 = 3 + 2 = 5
a_5 = 5 + 3 = 8
a_6 = 8 + 5 = 13
a_7 = 13 + 8 = 21
a_8 = 21 + 13 = 34
a_9 = 34 + 21 = 55
a_10 = 55 + 34 = 89
Alternatively, observe that a_n matches the Fibonacci sequence shifted by one index, so a_10 equals the 11th Fibonacci number, which is 89.
Answer: 89