1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – lulu Apr 12 '18 at 17:02
  • $\begingroup$ why does the remaining arrangements belong to $a_{n-1}$ if the top is red? $\endgroup$ – mt12345 Apr 12 '18 at 17:04
  • $\begingroup$ 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. $\endgroup$ – lulu Apr 12 '18 at 17:06
  • $\begingroup$ and then the same explanation for if it is blue or yellow? $\endgroup$ – mt12345 Apr 12 '18 at 17:08
  • $\begingroup$ Well, follow the same logic only know the blue (or yellow) flag has length $1$. $\endgroup$ – lulu Apr 12 '18 at 17:08
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks for this explanation, what would $a_1,a_2$ be? I am now trying to solve it $\endgroup$ – mt12345 Apr 12 '18 at 17:11
  • $\begingroup$ @mt12345: it is already there. $L_1=2$ and $L_2=5$. $\endgroup$ – Jack D'Aurizio Apr 12 '18 at 17:12
  • $\begingroup$ thanks for your help, I think I understand! $\endgroup$ – mt12345 Apr 12 '18 at 17:13
  • $\begingroup$ is there no $a_0$? $\endgroup$ – mt12345 Apr 12 '18 at 17:38
  • $\begingroup$ shouldn't $a_0=1$? $\endgroup$ – mt12345 Apr 12 '18 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.