A flagpole is $n$ feet tall. On this 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 of the flags is exactly $n$ feet. Let fn be the number of ways to display these flags on an $n$ foot tall flagpole.
a) Find $f_1$, $f_2$, $f_3$
b) Prove that $$ f_n = f_{n-1} + 2f_{n-2}, \forall n>=3 \in\mathbb{Z} $$
c) Prove by induction on $n$ that $$ f_n = \frac{2}{3} 2^n + \frac{1}{3} (-1)^n, \forall n>=1 \in\mathbb{Z}. $$
Here is what I have done so far: Based on the comments, Here is answer for part a):
$f_1$ = 1 (only 1 way to fit just 1 red)
$f_2$ = 3 (it is 2 feet, so there are 3 ways we can arrange the flags, either 2red, or 1blue, or 1green)
$f_3$ = 5 (either 3red, or 1red+1blue, 1blue+1red, 1red+1green, 1green+1red)
for $f_3$ we can use: $$ f_n = f_{n-1} + 2f_{n-2}, \forall n>=3 \in\mathbb{Z} $$ since 3>=3
So, $$f_3 = f_{3-1} + 2f_{3-2} => f_2 + 2f_1 => 3 + 2(1) = 5 $$
Brief answer: In principle we use strong induction, showing that if $f_k=\frac{2}{3}\cdot 2^k +\frac{1}{3}\cdot(-1)^k$ for any $k\lt n$, then $f_n=\frac{2}{3}\cdot 2^n+\frac{1}{3}\cdot (-1)^n$.
Note that $f_n=f_{n-1}+2f_{n-2}$. It follows by the induction assumption that $$f_n=\frac{2}{3}\cdot 2^{n-1}+\frac{4}{3}\cdot 2^{n-2}+\frac{1}{3}\cdot(-1)^{n-1}+\frac{2}{3}\cdot (-1)^{n-2}.$$ Now we simplify. We have $$\frac{2}{3}\cdot 2^{n-1}+\frac{4}{3}\cdot 2^{n-2}=\frac{2}{3}\cdot 2^{n-1}+\frac{2}{3}\cdot 2^{n-1}=\frac{2}{3}\cdot 2^n.\tag{1}$$
Also, $$\frac{1}{3}\cdot (-1)^{n-1}+\frac{2}{3}\cdot (-1)^{n-2}=\frac{2}{3}\cdot (-1)^n -\frac{1}{3}\cdot (-1)^n=\frac{1}{3}\cdot (-1)^n.\tag{2}$$ Together, (1) and (2) show that $f_n=\frac{2}{3}\cdot 2^n+\frac{1}{3}\cdot (-1)^n$.
Remark: It is not clear to me whether you know why the recurrence $f_n=f_{n-1}+2f_{n-2}$ holds. Imagine an arrangement of flags of total length $n$. Maybe the top flag is red. It can be followed by any arrangement of flags of total length $n-1$, and there are $f_{n-1}$ of these. Or maybe the top flag is blue or green ($2$ choices). For each choice, that top flag can be followed by any arrangement of flags of total length $n-2$, for a total of $2f_{n-2}$. That shows that $f_n=f_{n-1}+2f_{n-2}$.