Prove through induction that $P(\alpha)$ is true for all $\alpha \in \mathbb{N}$.

Question

From a previous question I found out a formula to work out the number of words I can create, that have a maximum length of $\alpha \in \mathbb{N}$, is

$$P(\alpha) = \frac{3^{\alpha+1}-1}{2}$$

Now I want to check that $P(\alpha)$ is true with induction.

Base Case: When $\alpha =0$, we have that $P(\alpha) = \frac{3^{0+1}-1}{2} = 1 = |\epsilon|$

Inductive Step: Assume that it holds for $P(\alpha)$ and prove that it works for $P(\alpha + 1)$

So we have $P(\alpha +1)= \frac{3^{(\alpha +1)+1}-1}{2}=\frac{3^{\alpha+2}}{2}=\frac{3^{\alpha+1} \cdot 3^1-1}{2}$

But I'm not sure how to continue on from here.

Answer 1

You have to take a word of maximum length $\alpha + 1$, either it is of maximum length $\alpha$, either it is of length $\alpha + 1$, thus: you have: $P(\alpha) + 3P(\alpha)$ words, this is the induction proof you're looking at.