<s>[INST] 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.
 [/INST] 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*}$
</s>