Knowing when a pattern is a linear homogeneous recurrence relation

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.

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}$$

• That's a clever way of doing it. Thank you! – user609600 Nov 7 '18 at 0:27

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*}