Number of paths in Cayley graph of free group / random walk on tree / Cayley graph of free group I want to calculate number of paths of $n$ "components" with length $k$ which goes in Cayley graph of free group $F_2$, i.e.:
$F_2 = <a, b, a^{-1}, b^{-1}> = <S>$ - free group with 2 generators, how much words $w = g_1 * ... * g_n, g_i \in S$, such that $l(w) = k$, where $l$ - length of word (we reduce our word to shortest and count all letters) exists?
I`d try to google "random walk on Cayler group of free group"/"word lengths in free group" and found nothing
I have next idea:

*

*Denote $p_n(g, h)$ - number of ways from vertex $g$ to vertex $h$. Then I have the following hypothesis (I don't know is it true, it looks correct, but I didn`t proof it yet): $p_n(g, h) = p_n(e, g^{-1}h)$ - depends only on length of $g^{-1}h$. I need that to calculate recurrence relation for $p_n(0, 0)$:

$p_n(0) = 4 * p_{n-2}(0) + p_{n-2}(2)$, where $p_n(k)$ - number of words $g_1 *...* g_n$ of length $k$ (i.e. if we reduce our word, it will have exactly $k$ letters)
And here I stuck:

*

*I didn`t proof the hypothesis yet (it looks like something trivial, but still)


*I only find recurrence relation for $p_n(0)$, but I want to find all $p_n(k)$
Any suggections?
 A: Your hypothesis is trivially true: a walk from $g$ to $h$ is found by taking a walk from $0$ to $g^{-1}h$, and left multiplying all steps by $g$. This is bijective, with inverse map of
Finding a recurrence for all $n,k$ was quite tricky to think about, because there is a special case when $k=1$. Here is a recurrence which works for all $n,k$:
$$
p_{n}(k)=\begin{cases}
3p_{n-1}(k-1)+p_{n-1}(k+1) & k\neq 1\\
4p_{n-1}(0)+p_{n-1}(2) & k = 1
\end{cases}
$$
To explain, consider a string $s$ whose un-reduced length is $n$, which reduces to a string $r$ with length $k$. Let $s'$ be the result of deleting the first entry of $s$, and let $r'$ be the reduced version of $s'$.

*

*If the first symbol of $s$ is the opposite of the first symbol of $r'$, then $r'$ must have length $k+1$. Such strings are counted by $p_{n-1}(k+1)$.


*If the first symbol of $s$ is the not the opposite of the first symbol of $r'$, then $r'$ must have length $k-1$. There are three choices for the first symbol, so these are counted by $3p_{n-1}(k-1)$.


*Finally, if $r'$ is the empty string, then the first symbol of $s$ can be any of four choices.
