Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal.
I have to use induction for this, and have to provide two examples of regular expressions S and T such that (ST)* and S*T* are NOT equal.
How would I go about doing this? I think my base case would be with the empty set for S and T and then my inductive step would assume that those are true, but then I do not know where to go from there.
Any help is great, thank you.
Here are some ideas to get you going.
Words over a one-letter alphabet are distinguished only by their lengths. If $R$ is any regular expression for that alphabet, let $L_R$ be the set of lengths of words corresponding to $R$. The words in $ST$ are exactly those whose lengths are of the form $s+t$ for some $s\in L_S$ and $t\in L_T$: we could express this by writing $L_{ST}=L_S+L_T$.
What is $L_{(ST)^2}$? $(ST)^2=STST$, so the words in $(ST)^2$ have lengths of the form $s_1+t_1+s_2+t_2$, where $s_1,s_2\in L_S$ and $t_1,t_2\in L_T$. Conversely, if you start with any $s_1,s_2\in L_S$ and $t_1,t_2\in L_T$, there is a word of that length in $(ST)^2$. But
$$s_1+t_1+s_2+t_2=s_1+s_2+t_1+t_2\;,$$
so you can also find a word of that length in $S^2T^2$. Similarly, starting with a word in $S^2T^2$, you can find one of the same length in $(ST)^2$. Thus, $L_{S^2T^2}=L_{(ST)^2}$. But words of the same length over a one-letter alphabet are the same word, so $(ST)^2=S^2T^2$.
Now generalize this to $(ST)^n$ and $S^nT^n$ for arbitrary $n\in\Bbb N$; you won’t need an induction argument, unless you’re required to prove that
$$\sum_{k=1}^n(s_k+t_k)=\sum_{k=1}^ns_k+\sum_{k=1}^nt_k$$
for all $n\in\Bbb N$ and all $s_k,t_k\in\Bbb N$ for $k=1,\ldots,n$.
For the second part, there’s a simple example with $S=T$, both being just about the simplest possible regular expression that generates a non-empty word. For that example $(ST)^*$ generates a proper subset of $S^*T^*$.