Consider a countable alphabet $A = \{a_{1},a_{2},... \}$. Let $L_{k}$ be the language over $A$ consisting of those words $w$ such that the sum of the subscripts of the letters in $w$ is equal to $k$. Show that $L_{k}$ is finite.
I have tried:
- $A = a_{1}$ implies $L(a_{1})$ is finite.
- $A = a_{2}$ implies $L(a_{2})$ is finite.
- ...
- $A = a_{n}$ implies $L(a_{n})$ is finite.
Therefore the union: $L(a_{1}) \cup L(a_{2}) \cup \cdots \cup L(n)$ is finite.
Am I doing this right or is there a more formal and better way to solve it?
Since each number $k$ has $2^{k-1}$ distinct compositions, $L_{k}$ will contain $2^{k-1}$ elements. Since for any $n ∈ \mathbb{N}$, $2^{n-1} ∈ \mathbb{N}$, it follows that $L_{n}$ must be finite.