Solution: 2015 Fall Final - 6

Author: Michiel Smid

Question

Consider strings of characters, each character being $a$, $b$, or $c$, that contain at least one $a$. Let $S_n$ be the number of such strings having length $n$. Which of the following is true?

(a)

$S_n = n \cdot 3^{n-1}$

(b)

$S_n = 3^{n} - 2^{n}$

(c)

$S_n = 3^{n} - n$

(d)

$S_n = n \cdot 2^{n-1}$

Solution

We’re basically looking for the total number of strings of length $n$ excluding those that have no $a$s.

Let S be the set of all strings
The first character can be any of the 3 characters: 3
The second character can be any of the 3 characters: 3
...
The $n$th character can be any of the 3 characters: 3
$ |S| = 3^n $
Let A be the event that a string has no $a$s.
The first character can be any of the 2 characters: 2
The second character can be any of the 2 characters: 2
...
The $n$th character can be any of the 2 characters: 2
$ |A| = 2^n $

Now, let’s exclude the strings that contain no a’s

$ |S| - |A| = 3^n - 2^n $