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?
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$.
You are actually dealing with Pell numbers.