recurrence relation Homework question 1

Question

This is a HW question

1. Find the recurrent relations for $a_n, n\geq 0$ where $a_n$ is the number of $n$character upper case words that contain exactly one $A$

We are only required to find the relation and not solve it.

I believe its:

$a_0 = 1$

$a_1 = 26$

$a_2 = 25*26$

$a_3 = 25^2*26$

$a_4 = 25^3*26$

I guess I am wondering if I am right as Recurrence relation is a very new topic for me.

Answer 1

The idea is to find a relationship between $a_{n+1}$ and $a+n$ (and possibly earlier values).

Call an $n$-character word that contains exactly one A good. We calculate $a_n$, the number of good words of length $n$, for a small number of values of $n$. This is in principle not really necessary, we are only asked for the recurrence. However, it is always good to have cconcrete experience with what we are counting.

There are $0$ good words of length $0$.

There is exactly $1$ good word of length $1$.

As for length $2$, let's list them. There are the words AX, where X is anything other than A, and XA, same restriction, total $50$.

But we want a recurrence. The idea is that we get a formula for $a_{n+1}$ that possibly involves $a_n$, and perhaps even earlier values.

We can make a good word of length $n+1$ in $2$ ways: (i) by taking a good word of length $n$, and appending any letter other than A or (ii) by taking an $n$-character word without any A's, and appending an A.

There are $25a_n$ good Type (i) words of length $n+1$. For any of the $a_n$ good words of length $n$ can be extended in $25$ ways. . There are $25^n$ good Type (ii) words of length $n+1$. Foer there are $25^n$ words of length $n$ that have no A.

It follows that $$a_{n+1}=25a_n+25^n.$$

Answer 2

The recurrence André Nicolas' answer provides can be solved by using generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$, sum over $n \ge 0$, and write the result in terms of $A(z)$: $$ \frac{A(z) - a_0}{z} = 25 A(z) + \frac{1}{1 - 25 z} $$ This can be solved for $A(z)$: $$ A(z) = \frac{1}{25 (1 - 25 z)^2} - \frac{1}{25 (1 - 25 z)} $$ Using the generalized binomial theorem: \begin{align} a_n &= \frac{1}{25} \binom{-2}{n} (-1)^2 \cdot 25^n - \frac{1}{25} \cdot 25^n \\ &= \left( \binom{n + 2 - 1}{2 - 1} - 1 \right) \cdot 25^{n - 1} \\ &= n \cdot 25^{n - 1} \end{align}