Why can't you use the fact that fₙ = 2fₙ₋₁ + 2fₙ₋₂ because it is the number of ways to tile a 1x7 strip?

[spaceblastxy1428]

Why can't you use the fact that $f(n)=2f(n-1)+2f(n-2))$ because it is the number of ways to tile a $1 \times 7$ strip using $\fbox{B}, \fbox{R}, \fbox{W}\fbox{R}, \fbox{W}\fbox{B}?$ You get the recursion $2, 6, 16, 44, 120, 328, 896,$ and then you divide it by $2$ because it can end in $W$ or $B$ to get $\fbox{448}$

[debbie]

@spaceblastxy1428 Yes, great! That is also another way to solve this problem. Excellent!

It is clever to think of tiling a $1 \times 7$ strip with $\fbox{B}, \fbox{R}, \fbox{W}\fbox{R}, \text{ and } \fbox{W}\fbox{B}$ because here we don't have a single white tile; the whites are always stuck next to a non-white, so we are guaranteed to not have two whites side-by-side.

 

We can make a strip of length $n$ by adding a $\fbox{B} \text{ or } \fbox{R}$ to the end of a strip of length $n-1.$ We don't have to worry about what the last colored bead is, since we aren't adding a white bead.

$$\ldots \boxed{ n-4^{\text{th}}} , \boxed{ n-3^{\text{rd}}}, \boxed{ n-2^{\text{nd}}}, \boxed{n-1^{\text{st}}}, \fbox{B}$$

$$\ldots \boxed{ n-4^{\text{th}}} , \boxed{ n-3^{\text{rd}}}, \boxed{ n-2^{\text{nd}}}, \boxed{n-1^{\text{st}}}, \fbox{R}$$

$$\text{ 2 ways starting from length } n-1$$

 
We could also make a strip of length $n$ by adding a $\fbox{W}\fbox{R} \text{ or } \fbox{W}\fbox{B}$ to the end of a strip of length $n -2.$ This strip is $n-2$ in length instead of $n-1$ in length because the tile we are adding is $2$ units long.

$$\ldots \boxed{ n-5^{\text{th}}} , \boxed{ n-4^{\text{th}}} , \boxed{ n-3^{\text{rd}}}, \boxed{ n-2^{\text{nd}}}, \fbox{W}\fbox{R}$$

$$\ldots \boxed{ n-5^{\text{th}}} , \boxed{ n-4^{\text{th}}} , \boxed{ n-3^{\text{rd}}}, \boxed{ n-2^{\text{nd}}}, \fbox{W}\fbox{B}$$

$$\text{ 2 ways starting from length } n - 2$$
 

This is expressed by the recursive formula

$$f_n = 2 f_{n-1} + 2f_{n-2}$$

or $$f_n = 2 \left( f_{n-1} + f_{n-2} \right)$$

where $f_n =$ ways to make a sequence of $n$ beads, $f_{n-1} =$ ways to make a sequence of $n-1$ beads, and $f_{n-2} =$ ways to make a sequence of $n-2$ beads.

Now we just need to find the number of strips for the small cases, since the recursive formula doesn't work for very small $n.$

• For $n = 1, \text{ a } \text{ } 1 \times 1$ strip:

There are $2$ ways: $\fbox{R} \text{ or } \fbox{B}.$

• For $n = 2, \text{ a } \text{ } 1 \times 2$ strip:

There are $6$ ways:

$$\fbox{R}, \fbox{R}$$

$$\fbox{R}, \fbox{B}$$

$$\fbox{B}, \fbox{R}$$

$$\fbox{B}, \fbox{B}$$

$$\fbox{W}\fbox{R}$$

$$\fbox{W}\fbox{B}$$

Now we have enough values to start our recursion.

$$\begin{aligned} f_3 &= 2 \left( f_2 + f_1 \right) \\ &= 2( 2 + 6) \\ &= 16\\ \\ f_4 &= 2 \left( f_3 + f_2 \right) \\ &= 2 (16 + 6) \\ &= 44\\ \\ f_5 &= 2\left( f_4 + f_3 \right) \\ &= 2(44 + 16) \\ &= 120 \\ \\ f_6 &= 2 \left( f_5 + f_4 \right) \\ &= 2 (120 +44 ) \\ &= 328 \\ \\ f_7 &= 2 \left( f_6 + f_5 \right) \\ &= 2(328 + 120) \\ &= 2 \times 448 \\ \\ \end{aligned}$$

Thus $2 \times 448$ is the number of $1\times 7$ strips, but we want the number of $1 \times 6$ strips, so what should we do now? There are some copies that we should throw away. These copies have the same first $6$ beads as another way, with only the last bead being different.

$$\ldots \boxed{ S} , \boxed{ A} , \boxed{ M} , \boxed{ E}, \boxed{ \text{ beads} }, \fbox{W}$$
$$\ldots \boxed{ S} , \boxed{ A} , \boxed{ M} , \boxed{ E}, \boxed{ \text{ beads} }, \fbox{B}$$

Removing the last bead of each string would give us the same $1 \times 6$ beads. There is no restriction on $W$ or $B,$ so there are equal numbers of strings ending in $W,$ and equal numbers of strings ending in $B.$ Thus we want half of the number of $1 \times 7$ strips, and the answer is

$\frac{2 \times 448 }{2} = \boxed{448 \text{ ways }}$ to color 6 beads black, white or red if two whites cannot be next to each other.