# Recurrence relation over a finite alphabet

Let $$A_n$$ be the set of all finite words over the alphabet $$\{1,2,3\}$$ whose digits sum to $$n$$. I am trying to find a recurrence relation with initial conditions for $$|A_n|$$. I have checked the first few $$n$$ and got that $$|A_1|=1$$ , $$|A_2|=2$$, $$|A_3|=4$$, $$|A_4|=7$$, $$|A_5|=13$$, $$|A_6|=24$$. I can't seem to find a pattern that allows me to create a recurrence relation, nor I am I sure how I could check that such a pattern would be correct.

## 2 Answers

To set up a recurrence, note that to get a sequence with value $$n$$ you add a one to one of the sequences giving $$n - 1$$, a two to a $$n - 2$$ or a three to $$n - 3$$. So the number $$S_n$$ of sequences with value $$n$$ satisfies:

\begin{align*} S_n &= S_{n - 1} + S_{n - 2} + S_{n - 3} \end{align*}

For initial values, we have $$S_0 = 1$$ (the empty sequence), $$S_1 = 1$$ (just $$1$$), $$S_2 = 2$$ (sequences $$11, 2$$), $$S_3 = 4$$ ($$111, 12, 21, 3$$).

We see that this is just shifted tribonacci numbers (they satisfy the same recurrence, but with $$T_0 = T_1 = 0, T_2 = 1$$). So $$S_n = T_{n + 2}$$.

A way to solve this is by using generating functions.

A single digit has weight 1, 2 or 3, so it is represented by $$z + z^2 + z^3$$, we want a sequence of those, that is:

\begin{align*} 1 + (z + z^2 + z^3) + (z + z^2 + z^3)^2 + \dotsb &= \frac{1}{1 - (z + z^2 + z^3)} \\ &= \frac{1}{1 - z - z^2 - z^3} \end{align*}

Consider the tribonacci sequence:

\begin{align*} T_{n + 3} &= T_{n + 2} + T_{n + 1} + T_n \qquad T_0 = T_1 = 0, T_2 = 1 \end{align*}

It's generating function is:

\begin{align*} T(z) &= \sum_{n \ge 0} T_n z^n \\ &= \frac{z^2}{1 - z - z^2 - z^3} \end{align*}

We see that:

\begin{align*} \sum_{n \ge 0} T_{n + 2} z^n &= \frac{T(z) -T_0 - T_1 z - T_2 z}{z^2} \\ &= \frac{1}{1 - z - z^2 - z^3} \end{align*}

So the number of sequences that sum to $$n$$ is $$T_{n + 2}$$.