recurrence relation Homework question 1 This is a HW question


*

*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.
 A: 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.$$
A: 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}
