# Explanation of a recurrence relation in combinatorics

I have the answer to the following question but I am not sure how this answer was solved. I am looking for some help with this explanation, thanks!

Find the recurrence relation for the number of ways to arrange flags on an $n$-foot flagpole using the three types of flags: red flags $2$ foot high, yellow flags $1$ foot hight and blue flags $1$ foot high

The solution is: $a_{n+1} = 2a_n + a_{n-1}$

My thinking was to consider cases, where it starts with a blue flag, or starts with a yellow flag or starts with a red flag.

And what are the initial conditions of this recurrence relation?

• Well, the top flag is either red, blue or yellow. If it is red then the remaining arrangement belongs to $a_{n-1}$. If it is blue or yellow, the remaining arrangement belongs to $a_{n}$. – lulu Apr 12 '18 at 17:02
• why does the remaining arrangements belong to $a_{n-1}$ if the top is red? – mt12345 Apr 12 '18 at 17:04
• Because the red flag is $2$ feet long so, if the total length is $n+1$ then the other flags must take up $n+1-2=n-1$ feet. – lulu Apr 12 '18 at 17:06
• and then the same explanation for if it is blue or yellow? – mt12345 Apr 12 '18 at 17:08
• Well, follow the same logic only know the blue (or yellow) flag has length $1$. – lulu Apr 12 '18 at 17:08

This is the same as counting the strings with length $n$ over the alphabet $\Sigma=\{RR,Y,B\}$.
Let us denote their number as $L_n$. We have $L_1=2$ (strings $Y$ and $B$), $L_2=5$ (strings $YY,BB,YB,BY,RR$) and for any $n\geq 3$ $$L_{n} = 2 L_{n-1}+L_{n-2}$$ by considering the removal of the first symbol in a string with length $n$. If the first symbol is $RR$ the truncated string is a valid string with length $n-2$, if the first symbol is $Y$ or $B$ the truncated string is a valid string with length $n-1$. Conversely, each string with length $n$ can be obtained by pre-pending $RR$ to a string with length $n-2$, or by pre-pending $Y$ or $B$ to a string with length $n-1$.
By the generating functions machinery, $L_n$ behaves like $C\cdot(1+\sqrt{2})^n$ for large values of $n$.
• thanks for this explanation, what would $a_1,a_2$ be? I am now trying to solve it – mt12345 Apr 12 '18 at 17:11
• @mt12345: it is already there. $L_1=2$ and $L_2=5$. – Jack D'Aurizio Apr 12 '18 at 17:12
• is there no $a_0$? – mt12345 Apr 12 '18 at 17:38
• shouldn't $a_0=1$? – mt12345 Apr 12 '18 at 17:44