# Number of words in $\{pi,po\}^*$ of length at most 9

I have a language $L^*$ for $L = \{pi,po\}$ (I think pi counts as one letter and po also as one letter otherwise a max length of 9 is not possible).

The question is how many words I can make with $L^*$ where the maximum length is 9.

The answer is 31, but I do not know how it got calculated. How is this calculated?

• Both $pi$ and $po$ count as two letters for the answer to be correct. Can you count how many strings of length $n$ you can form? – quicksort Apr 5 '18 at 19:03
• @quicksort so $pipo$ would be 4 letters then right? – Diceble Apr 5 '18 at 19:10
• @quicksort and after thinking i would have no idea how to count that... – Diceble Apr 5 '18 at 19:15
• How many strings of length $n$ made of zeroes and ones are there? – quicksort Apr 5 '18 at 19:22
• is it 2^n ? sorry if I'm totally wrong, but I just miss something where i proberly would facepalm myself if I found it out. – Diceble Apr 5 '18 at 19:34

Here are all words in $L^*$ of length at most 9: $$\epsilon, \\ pi, po, \\ pipi, pipo, popi, popo, \\ pipipi, pipipo, pipopi, pipopo, popipi, popipo, popopi, popopo, \\ pipipipi, pipipipo, pipipopi, pipipopo, pipopipi, pipopipo, pipopopi, pipopopo, popipipi, popipipo, popipopi, popipopo, popopipi, popopipo, popopopi, popopopo.$$ In total, there are 31 words.
More generally, suppose that we have $m$ distinct words of length $\ell$. Then the total number of words of length at most $n$ is $$\sum_{r=0}^{\lfloor n/\ell \rfloor} m^r = \frac{m^{\lfloor n/\ell \rfloor+1}-1}{m-1}.$$ In our case, we get $\frac{2^{\lfloor 9/2 \rfloor + 1}-1}{2-1} = 2^{4+1}-1 = 31$.