2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ First, shouldn't it be $a_1 = 1$? Second, you are undercounting the number of words available, as for $n = 2$ for example, you have both AB..AZ and BA..ZA, which would be 50 different words. $\endgroup$ – Greebo Aug 7 '13 at 14:07
  • $\begingroup$ I think you meant BA...ZA. Did you? $\endgroup$ – pitchounet Aug 7 '13 at 14:09
  • $\begingroup$ Yeah, and I had the number wrong as well. $\endgroup$ – Greebo Aug 7 '13 at 14:10
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ thanks Andre.. I was really off on this one. $\endgroup$ – Kj Tada Aug 7 '13 at 14:15
  • 1
    $\begingroup$ You are welcome. By the way, using (at least internally) words like good or bad can be surprisingly useful, in that it can make things feel more concrete. $\endgroup$ – André Nicolas Aug 7 '13 at 14:30
0
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.