Knowing when a pattern is a linear homogeneous recurrence relation

Question

I'm quite stuck on finding a pattern here:

Suppose we have:

• 1 inch letters: f, i, t
• 2 inch letters: a, c, d, e, g, n, o, p, s, u

And we want to find a recurrence relation for making a banner of length $n$ inches. We can repeat letters and order matters. So "ff" would count as 1 way and "cs" and "sc" are both valid ways too.

Essentially I can write things in the form:

(ways to make with just 1s) + (ways to make with just 2s) + (ways to make with both)

So:

• n = 0: 1 way
• n = 1: 3 ways
• n = 2: $3^2 + 10 = 19$ ways
• n = 3: $3^3 + 2*(3*10)=87$ ways
• etc.

Somebody suggested the form $A_{n} = xA_{n-1} + yA_{n-2}$ and I solved a system of equations using this form to find x and y. This turned out to be the correct answer but he did not explain where he got this from. The answer was:

$$A_0 = 1\\A_1 = 3\\A_n = 3A_{n-1} + 10A_{n-2}, n\geq2$$

I can see it is the form of a linear homogeneous recurrence relation but I don't know how he spotted the pattern in doing calculations of different banners of length $n$. How do we know to use the form of a linear homogeneous recurrence relation? I'm not interested in solving the recurrence relation, only in finding it.

Answer 1

Look at it that way: You can construct an $n$-inch banner in two ways:

a) Write an $n-1$-inch banner and and add one of the $1$-inch letters. For this you have $3A_{n-1}$ (number of $1$-inch letters times number of possibilities for the $n-1$-inch banner)

b) Write an $n-2$-inch banner and add one of the $2$-inch letters. ($10A_{n-2}$ possibilities) This leads to the recursion $$A_n=3A_{n-1}+10A_{n-2}$$

Answer 2

To complete @weee's solution, use generating functions. Note that $A_0 = 1$ (just one empty banner) and $A_1 = 3$ (number of one-inch banners). Define $g(z) = \sum_{n \ge 0} A_n z^n$, write your recurrence as:

$\begin{equation*} A_{n + 2} = A_{n + 1} + 10 A_n \end{equation*}$

Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize some sums:

$\begin{align*} \sum_{n \ge 0} A_{n + 2} z^n &= 3 \sum_{n \ge 0} A_{n + 1} z^n + 10 \sum_{n \ge 0} A_n z^n \\ \frac{g(z) - A_0 - A_1 z}{z^2} &= 3 \frac{g(z) - A_0}{z} + 10 g(z) \\ \frac{g(z) - 1 - 3 z}{z^2} &= 3 \frac{g(z) - 1}{z} + 10 g(z) \end{align*}$

Solve for $g(z)$, as partial fractions:

$\begin{align*} g(z) &= \frac{1}{1 - 3 z - 10 z^2} \\ &= \frac{5}{7} \cdot \frac{1}{1 - 5 z} + \frac{2}{7} \cdot \frac{1}{1 + 2 z} \end{align*}$

From here we read the coefficients directly:

$\begin{align*} A_n &= [z^n] g(z) \\ &= \frac{5}{7} \cdot 5^n + \frac{2}{7} \cdot (-2)^n \\ &= \frac{5^{n + 1} - (-2)^{n + 1}}{7} \end{align*}$