Recurrence relation for total no of n length English letter words, with even no of a’s

Question

The recurrence relation for total no of n length English letter words, with even no of a’s.

Below is some parts I could build -

Assumptions - 26 english letters and no epsilon

Let us assume a string of length n and positions from (1 to n)

Let T(n) denote the number of strings with length 'n' containing even number of a's

Now, T(n) = Number of String of length 'n' that do not with 'a' + Number of String of length 'n' ending with 'a' 

Let T(n) = Part1 + Part2 

Part1 :

If a strings does not end with 'a' then it means string of length (n-1) has even number of a's and can be permuted in T(n-1) ways.

Thus the n^th position can be filled only with the remaining 25 letters except 'a' then below is the conclusion -

Number of String of length 'n' that do not with 'a' = 25* T(n-1) 

Part2 :

If a string ends with 'a' then the string of length (n-1) that is except position n^th should contain odd number of a^'s so that end result will be even number of a^'s

There is only 1 possibility for n^th position and for upto length (n-1) we should have odd 'a's

Could someone please guide how to proceed further and if things are correct till here?

Answer 1

Two cases:

case1: The word starts with 'a'

case2: The word doesnt start with 'a'

 

Let the 'n' letter words containing even no. of 'a' be given by T(n).

 

If word doesnt start with 'a',  total words = $\binom{25}{1}*T(n-1)$

 

If word starts with 'a' , total words

= $26^{n-1}$ - No. of 'n-1' letter words containing even no. of 'a'

= $26^{n-1}$ - T(n-1)

 

$\therefore$ T(n) = $\binom{25}{1}*T(n-1)$ +  [ $26^{n-1}$ - T(n-1) ]

Comments

@Sushant thanks.