Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given an integer $k$, and $S$ a finite subset of $L$ define recursively the following sequence of subsets of $L$: $$\begin{align} A_1 &=S\cup \{\epsilon\} \\ A_{n+1} &=\left\{\prod_{i=1}^ka_i^{n_i}\Big/a_i\in A_n, n_i\in \Bbb{N}\right\}\end{align}$$
My question:
For each integer $n$ there exists a polynomial $P$ such that the number of words of length $h$ in $A_n$ is less or equal to $P(h)$.
Example if $S=\left\{\epsilon,0,1\right\}$ and $k=2$ then $$A_2=\left\{\prod_{i=1}^2a_i^{n_i}\Big/a_i\in S \right\}=\left\{0^n1^m,1^n0^m/n,m\in\Bbb N\right\}$$ and the number of words of length $h$ is $2h+2$.
If $S$ is finite then I can prove that $A_2$ contains no more than $|S|\dbinom{|S|+k-1}{k-1}$, but how can I prove a similar result for $A_n$.
Thanks for your help.
HINT: A word of length $h$ in $A_{n+1}$ is a composition of words of $A_n$, each of which must obviously have length at most $h$. There is a polynomial $P_n$ such that $A_n$ has at most $\sum_{i=0}^nP_n(i)$ words of length at most $h$, so you’re essentially working with an alphabet of size at most $\sum_{i=0}^nP_n(i)$.