016. Number of Cases and Recurrence Relation

Consider the situation of making words with only three letters: $a$, $b$, and $c$. If the letters $a$ and $b$ cannot be arranged adjacent to each other, find the number of all words whose length is $n$.

---

Let $A_n$ be the answer to find, and set $A_0 = 1$. Also, trivially, $A_1 = 3$.

Now, if $n \ge 2$, it can be classified as follows.

• (1) There is $c$ in the first position.
  • Excluding $c$, it is the same as the number of cases to create a word with the remaining $n - 1$ letters.
  • So, $A_{n - 1}$.
• (2) $c$ appears for the first time in the $k$-th position where $2 \le k \le n$.
  • $a$ and $b$ must appear alternately up to the $k-1$-th time.
  • Excluding the first $k$ letters, the rest is equal to the number of cases to make a word with $n - k$ letters.
  • So, $2 A_{n - k}$.
• (3) There is no $c$.
  • The only two cases are acceptable: $aba...$ and $bab...$
  • So, $2$.

Putting together the above, the recurrence relation is as follows. $$\begin{aligned} A_n &= A_{n-1} + 2 A_{n-2} + \cdots + 2 A_0 + 2 \\ A_{n-1} &= A_{n-2} + 2 A_{n-3} + \cdots + 2 A_0 + 2 \\ A_n - A_{n-1} &= A_{n-1} + A_{n-2} \\\\ \implies &A_n - 2 A_{n-1} - A_{n-2} = 0 \\ \implies &A_{n+1} - 2 A_n - A_{n-1} = 0 \quad (n \ge 1) \end{aligned}$$

This form of recurrence relation can be solved as a quadratic equation. It is the same process as finding the general term of the Fibonacci sequence. If this relation is transformed into the following quadratic equation, a simultaneous equation can be established by finding the two roots $\alpha$ and $\beta$ of this equation. $$\begin{aligned} &A_{n+1} - 2 A_n - A_{n-1} = A_{n+1} - (\alpha + \beta) A_n + \alpha \beta A_{n-1} = 0 \\\\ \implies &x^2 - 2 x - 1 = 0 \\ \implies &\alpha = 1 - \sqrt{2}, \quad \beta = 1 + \sqrt{2}, \quad \alpha + \beta = 2, \quad \alpha \beta = -1 \end{aligned}$$ $$\begin{aligned} &\begin{cases} A_{n+1} - \alpha A_n = \beta \left( A_n - \alpha A_{n-1} \right) \\ A_{n+1} - \beta A_n = \alpha \left( A_n - \beta A_{n-1} \right) \\ \end{cases} \\\\ \implies &\begin{cases} A_{n+1} - \alpha A_n = \beta^n \left( A_1 - \alpha A_0 \right) = \beta^n \left( 3 - \alpha \right) \\ A_{n+1} - \beta A_n = \alpha^n \left( A_1 - \beta A_0 \right) = \alpha^n \left( 3 - \beta \right) \\ \end{cases} \\\\ \implies &\left( \beta - \alpha \right) A_n = \beta^n \left( 3 - \alpha \right) - \alpha^n \left( 3 - \beta \right) \end{aligned}$$

Since $\alpha \ne \beta$, $$\begin{aligned} A_n &= \frac{\beta^n \left( 3 - \alpha \right) - \alpha^n \left( 3 - \beta \right)}{\beta - \alpha} = \frac{\beta^n \left( 1 + \beta \right) - \alpha^n \left( 1 + \alpha \right)}{\beta - \alpha} \\\\ &= \frac{(1 + \sqrt{2})^n \left( 2 + \sqrt{2} \right) - (1 - \sqrt{2})^n \left( 2 - \sqrt{2} \right)}{2 \sqrt{2}} \\\\ &= \frac{(1 + \sqrt{2})^n \left( \sqrt{2} + 1 \right) - (1 - \sqrt{2})^n \left( \sqrt{2} - 1 \right)}{2} \\\\ &= \frac{(1 + \sqrt{2})^{n+1} + (1 - \sqrt{2})^{n+1}}{2} \quad (n \ge 1) \end{aligned}$$