Different sidewalks that can be laid using n $1 \times 1$ square white, blue and red tiles so that no two red tiles lie next to each other?

How many different sidewalks of length $$n \geq 1$$ can be laid using n $$1 \times 1$$ square tiles, given an unlimited supply of such tiles in white, blue and red colors so that no two red tiles lie next to each other?

We have that:

• $$f_1 = 3$$, we can choose white, blue or red tile;
• $$f_2 = 8$$, we can choose every combination from set: WW, BB, WB, BW, RB, BR, WR, RW (only RR can't be chosen);
• $$f_3 = 22$$, we can choose every combinatorion ($$3 \cdot 3 \cdot 3 = 27$$) besides RRR $$(1)$$, RR[not R] $$(2)$$, [not R]RR $$(2)$$, therefore there is: $$27 - 1 - 2 - 2 = 22$$;
• $$f_4 = 64$$, we can choose every combinatorion ($$3 \cdot 3 \cdot 3 \cdot 3 = 81$$) besides RRRR $$(1)$$, RR[not R][every possible] $$(6)$$, [not R][every possible]RR $$(6)$$, [not R]RR[not R] $$(4)$$ therefore there is: $$81 - 1 - 6 - 6 - 4 = 60$$;

Then I came up with an recursive formula: $$f_n = 2f_{n-1} + 2f_{n-2}$$. We take all the sequences without R on the last place - we can have W or B on the last place, therefore we have $$2f_{n-1}$$. Then we take all the sequences with R on the last place, those can't have R on the next-to-last place, therefore there is $$2f_{n-2}$$ of them. The formula works for $$f_3$$ and $$f_4$$ so I assume it's correct.

So I have:

• $$f_1 = 3$$,
• $$f_2 = 8$$,
• $$f_n = 2f_{n-1} + 2f_{n-2}$$.

I calculate: $$f_n = 2f_{n-1} + 2f_{n-2} \iff f_n - 2f_{n-1} - 2f_{n-2} = 0$$

$$x^2 - 2x - 2 = 0 \implies \Delta = 4 - 4 \cdot 1 \cdot (-2) = 12 \implies \sqrt{\Delta} = 2\sqrt{3}$$

$$x_1 = \frac{2 + 2\sqrt{3}}{2} = 1 + \sqrt{3} \$$ and $$\ x_2 = \frac{2 - 2\sqrt{3}}{2} = 1 -\sqrt{3}$$

$$f_n = a(1 + \sqrt{3})^n + b(1 - \sqrt{3})^n$$ so:

1. $$a(1 + \sqrt{3}) + b(1 - \sqrt{3}) = 3 \iff a + \sqrt{3}a + b - \sqrt{3}b = 3$$
2. $$a(1 + \sqrt{3})^2 + b(1 - \sqrt{3})^2 = 8 \iff a(1 + 2\sqrt{3} + 3) + b(1 - 2\sqrt{3} + 3) = 8 \iff 2a + \sqrt{3}a + 2b - \sqrt{3}b = 4$$

By subtracting first equation from second one we get:

$$a + b = 1 \iff a = 1 - b$$

$$1 - b + \sqrt{3}(1 - b) + b - \sqrt{3}b = 3 \iff b = \frac{1}{2} - \frac{\sqrt{3}}{3}$$

$$a = 1 - \frac{1}{2} + \frac{\sqrt{3}}{3} = \frac{1}{2} + \frac{\sqrt{3}}{3}$$

So:

$$f_n = (\frac{1}{2} + \frac{\sqrt{3}}{3})(1 + \sqrt{3})^n + (\frac{1}{2} - \frac{\sqrt{3}}{3})(1 - \sqrt{3})^n$$

Is that correct?

• OEIS: A028859 Number of words of length $n$ without adjacent $0$s from the alphabet $\{0,1,2\}$ Commented Aug 12, 2023 at 23:19

Your solution is correct. We first deduce the recurrence. The total number of ways $$t_n$$ we can tile the sidewalk of length $$n$$ with no two adjacent red tiles is $$t_n = w_n + b_n + r_n$$ with:

$$w_n = w_{n - 1} + b_{n - 1} + r_{n - 1}$$ $$b_n = w_{n - 1} + b_{n - 1} + r_{n - 1}$$ $$r_n = w_{n - 1} + b_{n - 1}$$

where $$w_n$$ is the number of ways the sidewalk is tiled such that the $$n$$th tile is white. Similarly $$b_n$$ and $$r_n$$ are the number of ways the sidewalk is tiled such that the $$n$$th tiles are blue or red, respectively. We can simplify the above recurrences by noting that $$w_n = b_n$$ and so the system reduces to:

$$b_n = 2b_{n - 1} + r_{n - 1}$$ $$r_n = 2b_{n - 1}$$

which can be simplified further to:

$$b_n = 2b_{n - 1} + 2b_{n - 2}$$

which means the total number of ways to tile the sidewalk is:

$$f_n = t_n = 2b_n + r_n = 2b_n + 2b_{n - 1} = b_{n+1}$$

with $$b_1 = 1$$ and $$b_2 = 3$$ and so we get:

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

with $$f_1 = 3$$ and $$f_2 = 8$$, which is the recurrence you obtained. You determined the solution to this recurrence to be:

$$f_n = \left(\frac{1}{2} + \frac{\sqrt{3}}{3} \right) \left(1 + \sqrt{3} \right)^n + \left(\frac{1}{2} - \frac{\sqrt{3}}{3} \right) \left(1 - \sqrt{3} \right)^n$$

$$f_n = \alpha \left(1 + \sqrt{3} \right)^n + \beta \left(1 - \sqrt{3} \right)^n$$

We verify the solution using induction:

$$f_n = 2f_{n - 1} + 2f_{n - 2}$$ $$= 2 \alpha \left(1 + \sqrt{3} \right)^{n - 1} + 2 \beta \left(1 - \sqrt{3} \right)^{n - 1} + 2 \alpha \left(1 + \sqrt{3} \right)^{n - 2} + 2 \beta \left(1 - \sqrt{3} \right)^{n - 2}$$ $$= 2 \alpha \left( \frac{2 + \sqrt{3}}{\left( 1 + \sqrt{3} \right)^2} \right) \left(1 + \sqrt{3} \right)^n + 2 \beta \left( \frac{2 - \sqrt{3}}{\left( 1 - \sqrt{3} \right)^2} \right) \left(1 - \sqrt{3} \right)^n$$ $$= \alpha \left(1 + \sqrt{3} \right)^n + \beta \left(1 - \sqrt{3} \right)^n$$

And so we conclude the solution to the recurrence is correct.