Proof of formula of the number of strings of length n for the alphabet ${a,b,c,d}$

$\begingroup$

Suppose I want to prove that the amount of strings of length $n$ for the alphabet ${a,b,c,d}$, where every string has an even amount of $a$ satisfies the formula $f(n+1)= 2 f(n) + 4^n$. I wish to do this via induction, for the base cases we know that $f(0)=1$ since the empty string contain an even amount of strings. Also we know that for $f(1)=3$. Since the set would be $\{b,c,d\}$. we thus have our base case: $f(1)=2+1=3 $. Check. I know wish to do the inductive step, so given it holds for $k$, I want to prove it holds for $k+1$, I probably need to find a way to use the fact that we have an even amount of $a$. Every other letter we can just add randomly to every single word on $k+1$ positions, not quite sure how to use this yet....

$\endgroup$

2 Answers

$\begingroup$

HINT

There are $4^n$ different strings of length $n$ using $a$, $b$, $c$, or $d$.

So, if there are $f(n)$ strings of length $n$ with have an even number of $a$'s, then that means that there are $4^n-f(n)$ strings of length $n$ with an odd number of $a$'s.

I don't want to give it completely away, but this is a big hint ... I think with this you'll be able to complete the inductive step no problem ...

$\endgroup$ 3 $\begingroup$

Suppose that we already have all possible strings of length $n+1$ with even $a$'$s$. We will provide an argument by construction, by considering two cases: (1) Consider the first $n$ characters of such a string to contain an odd amount of $a$'$s$. We know there are $4^n$ words of length $n$, of which $f(n)$ contain an even amount of $a$'$s$. The amount of words of length $n$ with an odd amount of $a$'$s$ is thus $4^n - f(n)$, we can make these words even by simply putting an $a$ all the way in the back, thus we obtain $4^n - f(n)$ combinations in such manner.
(2) The other possibility is that the first $n$ characters already contained an even amount of $a$'$s$. We add $b, c, $ or $d$ to the end this word to obtain a new word with an even amount of $n$. In this manner we obtain $f(n) +f(n) + f(n)= 3 f(n)$ possible words. If we combine $(1)$ and $(2)$, we find that $$f(n+1)= 3 f(n)+4^n - f(n)= 2 f(n) + 4^n $$ As desired $\square$.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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