A flagpole is n feet tall. On this flag pole we display flags of the following types: red flags that are 1 foot tall, blue flags that are 2 feet tall and green flags that are 2 feet tall. The sum of the heights is exactly n feet.
Prove that there are exactly [(2/3)*(2^n)] + [(1/3)*(-1)^n] ways to display the flags.
Let d_n denote the number of possible ways to display the flags on an n-foot tall flagpole. Now the flag on top may be red, green, or blue. The number of possible ways to display the flags with a red one on top is ...
We derive by induction a formula for the number of ways flags of three different colors and two different heights can be displayed on a flagpole of a given fixed height.