Problem:
A Vitas word is a string of letters that satisfies the following conditions:
- It consists of only the letters , , .
- It begins with a and ends in an .
- No two consecutive letters are the same.
How many Vitas words are there with letters?
Solution
Solution:
Let be the number of -letter Vitas words that start with and end with .
Let us generalize and define:
- : number of -letter words starting with and ending with .
- : number of -letter words starting with and ending with .
We do not consider words ending with since the last letter cannot be (as the word must end with ).
For :
- The word must be (since it starts with and ends with ), so .
- The word is also possible, so .
For :
To form an -letter word ending with , the -th letter must be (since no two consecutive letters are the same), so we append to any -letter word ending with .
Thus,
Similarly, to form an -letter word ending with , the -th letter must be , so
But, at each step, the letter can be or (but not the same as the previous letter), so we must also consider that after the first , the rest of the letters alternate between and .
But, since the alphabet is only , , , and the first letter is , the rest of the letters (positions to ) are or , with no two consecutive letters the same.
Let us define as above, and as above.
From above:
With initial conditions:
(word ), (word ).
So,
So, for all , , ? But this cannot be, since the number should grow with .
Wait: Let's reconsider.
Let us define as the number of -letter words starting with and ending with .
Let as the number of -letter words starting with and ending with .
For :
Possible words: , .
So , .
For :
Words: , .
So (), ().
For :
Words: , .
So (), ().
So, for each , , .
But for :
Words: , .
So (), ().
So, for each , .
But this cannot be, since the number should be larger for .
Let us try to generalize differently.
Let us define as the number of -letter words starting with and ending with , where is or .
Let us consider the sequence of letters:
- The first letter is .
- The next letters are each or , with no two consecutive letters the same.
- The last letter is .
So, the word is , where each is or , and for .
Let us define as the number of sequences of length (positions to ), starting with ( or ), with no two consecutive letters the same.
But perhaps it's easier to let be the number of sequences of length (positions to ), with letters or , no two consecutive letters the same, and ending with .
Let be the number of such sequences of length ending with .
Let be the number of such sequences of length ending with .
We want , since the first letter is , and the rest is a sequence of letters, with the last letter , and no two consecutive letters the same.
The recurrence is:
- To get a sequence of length ending with , the previous letter must be , so .
- To get a sequence of length ending with , the previous letter must be , so .
With initial conditions:
For :
- The sequence is just one letter, which can be or .
So (sequence ), (sequence ).
Then:
b_2 = a_1 = 1
b_3 = a_2 = 1
So, for all , , .
But this cannot be, since the number should grow with .
Wait, perhaps the error is in the initial conditions.
Let us try to write out all possible sequences for small .
For :
-
For :
-
-
For :
-
-
For :
-
-
So, for , word.
For , words.
For , words.
For , words.
Wait, but for :
-
-
So, always words for .
But for :
-
-
So, the answer is .
Therefore, the number of Vitas words with letters is .