Recurrence Relations for Cosets in Free Groups

Let $F_2$ be the free group on two generators and let $H$ be a subgroup of $F_2$. We investigate a method for calculating the number of elements in a coset of $H$ that have a given length when written in reduced form. More specifically, taking $S_n\subseteq F_2$ to be the set of elements of length $n$, we show that for any coset $yH$ there always exists a recurrence relation of the form $$\mathrm{\mid }yH\cap S_n\mathrm{\mid }=\sum _{i=1}^{n-1}\sum _{xH\in F_2\mathrm{/}H}{a}_{i,xH}\cdot \mathrm{\mid }xH\cap S_{n-i}\mathrm{\mid }$$ for some constants $(a_{i,xH}{)}_{i\in \mathbb{N},xH\in F_2\mathrm{/}H}$, and we give an algorithm that calculates these constants. Further, we show that when $H$ has finite index and contains an element of odd length, only finitely many of the constants $a_{i,xH}$ are nonzero.