Random walk on the lamplighter group Consider a random walk on the lamplighter group with the following generating set: move left, move right, and toggle lamp. Start at the origin, with all lamps off. What is the probability that, after $t$ steps, the lamp at the origin is on?
I started by letting $g(b,k,t)$ denote the number of words of length $t$  that set the lamp at the origin to $b$ and the lamplighter at position $k$. Thus we have the recurrence relation
\begin{align*}
  g(b,k,0)&=[b=0][k=0] \\
  g(b,k,t+1)&=g(b,k-1,t)+g(b,k+1,t)+g(b \oplus [k=0],k,t)
\end{align*}
where $[\cdot]$ is the Iverson bracket and $\oplus$ is xor. Then I let $f(b,t)$ denote the number of words of length $t$ that set the lamp at the origin to $b$:
$$f(b,t) = \sum_{k \in \mathbb{Z}} g(b,k,t)$$
The answer to my question is $f(1,t) \cdot 3^{-t}$, since $3^t$ is the total number of words of length $t$. After some simplification, I obtained the following recurrence relation for $f$:
\begin{align*}
  f(b,0) &= [b=0] \\
  f(b,t+1) &= 3 f(b,t) - g(b, 0, t) + g(b \oplus 1, 0, t)
\end{align*}
I'm trying to get rid of the remaining $g$ terms. $g(0,0,t)$ and $g(1,0,t)$ represent the number of $t$-length words that return to the origin while leaving its lamp off or on, respectively. I suspect I might be able to use Motzkin paths to solve for these. The number of $t$-length words that return to the origin is the $t$th central trinomial coefficient. That is,
$$g(0,0,t)+g(1,0,t) = \sum_{i=0}^t \binom{t}{i} \binom{i}{t-i}$$
The first few coefficients are
\begin{array}{c|c|c}
& b = 0 & b = 1 \\
t=0 & 1 & 0 \\
t=1 & 0 & 1 \\
t=2 & 3 & 0 \\
t=3 & 2 & 5 \\
t=4 & 15 & 4 \\
t=5 & 22 & 29 \\
t=6 & 93 & 48 \\
t=7 & 196 & 197 \\
t=8 & 659 & 448 \\
t=9 & 1650 & 1489
\end{array}
EDIT: Let $L_k$ denote the set of words that shift the lamplighter by $k$. Then
$$[z^n]L_k(z) = \binom{n}{k}_2$$
where the RHS is the entry in row $n$ and column $k$ of the trinomial triangle. Let $L_k^-$ be the subset of $L_k$ such that the lamp at $k$ (or, equivalently in number, the lamp at the last position) is not toggled. Based on further investigation, it seems to be the case that
$$L_k^-(z) = L_k(z) \frac{1+z L_0(z)}{1+2z L_0(z)}$$
Is there a simple explanation for this relationship? I sense some kind of recursive definition of $L_k^-$ in terms of $L_k$, $L_0$, and $L_k^-$ itself.
 A: Motkzin paths indeed seem promising.
Consider that a word which ends at the origin must be of the form $(M0^*)^*$ where $M$ denotes a Motzkin path and $0$ denotes the lamp toggle. Alternatively, and perhaps more usefully, it must be of the form $0^*(M'0^*)^*$ where $M'$ denotes a non-empty Motkzin path.
The Motkzin numbers have g.f. $$A(x) = \frac{1 - x - \sqrt{1-2x-3x^2}}{2x^2}$$
but the offset is not quite what we want and we need to double to account for the first move being to the right or to the left, so for non-empty Motzkin paths we get g.f. $$A'(x) = 2x^2A(x) = 1 - x - \sqrt{1-2x-3x^2}$$
If we have $p$ non-empty Motkzin paths, that corresponds to $A'(x)^p$. Then we have $p+1$ gaps into which to insert the toggles at the origin, and we want an alternating sum because we're building towards $g(0, 0, t) - g(1, 0, t)$, so we want to convolve with a multinomial sequence $$\sum_{i=0}^\infty (-1)^i \binom{p+i}{p} x^i$$
Finally we sum over $p$ to get $$\begin{eqnarray}g(0, 0, t) - g(1, 0, t)
&=& [x^t] \sum_p \sum_{i=0}^\infty (-1)^i \binom{p+i}{p} x^i A'(x)^p \\
&=& [x^t] \sum_{i=0}^\infty (-x)^i \sum_p \binom{p+i}{p} A'(x)^p \\
&=& [x^t] \sum_{i=0}^\infty \frac{(-x)^i}{(1 - A'(x))^{i+1}} \\
&=& [x^t] \frac{1}{1 - A'(x)} \sum_{i=0}^\infty \left(\frac{-x}{1 - A'(x)}\right)^i \\
&=& [x^t] \frac{1}{1 - A'(x)} \frac{1}{1 - \left(\frac{-x}{1 - A'(x)}\right)} \\
&=& [x^t] \frac{1}{1 + x - A'(x)} \\
&=& [x^t] \frac{1}{2x + \sqrt{1-2x-3x^2}} \\
\end{eqnarray}$$

Now to get a recurrence we set $G(x) = \frac{1}{2x + \sqrt{1-2x-3x^2}}$ or $$G(x)\left( 2x + \sqrt{1-2x-3x^2} \right) = 1$$
I'm not entirely sure what the best way is to tackle that square root, but factoring as $1 - 2x - 3x^2 = (1 - 3x)(1 + x)$ seems like a plausible option. 
Then $$G(x)\left( 2x + \sum_{i=0}^\infty \binom{1/2}{i}(-3x)^i \sum_{j=0}^\infty \binom{1/2}{j}x^j \right) = 1$$
A change of variables probably helps: let $n = i + j$ and $$G(x)\left( 2x + \sum_{n=0}^\infty \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i x^n \right) = 1$$
Extracting a couple of small values of $n$ from the sum we get $$\sum_{n=0}^\infty \sum_{i=0}^n \ldots = 
1 - x + \sum_{n=2}^\infty \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i x^n$$ which substituting back in gives
$$G(x)\left( 1 + x + \sum_{n=2}^\infty \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i x^n \right) = 1$$
So comparing coefficients of $x^0$ we have $g_0 = 1$, and comparing coefficients of $x^1$ we have $g_0 + g_1 = 0$, or $g_1 = -1$.
Comparing coefficients of $x^t$ we have $$[x^t]G(x)\left( 2x + \sum_{n=0}^\infty \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i x^n \right) = [t = 0]$$ giving recurrence $$\sum_{n=0}^t g_{t-n} \left( 2[n = 1] + \sum_{i=0}^n \binom{1/2}{i}\binom{1/2}{n-i} (-3)^i \right) = [t = 0]$$ 
However, this is no more efficient to calculate than your original recurrence for $g(b,k,t)$, so the main interest is in using the generating function to analyse asymptotic behaviour.

Postscript: we can use $G$ to derive the generating function $F$ for $f(0, t)$ as follows:
$$\begin{eqnarray*}
f(0,0) &=& 1 \\
f(0,t+1) &=& 3 f(0,t) - [x^t]G(x)
\end{eqnarray*}$$
So $g_t x^t$ in $G$ becomes $-g_t x^{t+1} -3g_t x^{t+2} - 3^2 g_t x^{t+3} - \ldots = g_t x^t \frac{-x}{1-3x}$ and $$F(x) = \frac{1 - xG(x)}{1-3x}$$
