GATE 2014 CS (CS1) – Question 59
A pennant is an ordered sequence of 1s and 2s; an n-pennant has sum n. For example (1,1,2) is a 4-pennant. The 1-pennants are {(1)}, 2-pennants {(2),(1,1)}, and 3-pennants {(2,1),(1,1,1),(1,2)}. (1,2) differs from (2,1). Find the number of 10-pennants.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 88.9 to 89.1
Explanation
Let a_n count sequences totalling n. The final element is1 or2, giving a_n=a_(n−1)+a_(n−2), with a₀=1,a₁=1. Successive values are2,3,5,8,13,21,34,55,89 through n=10. Hence **89** distinct10-pennants.