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