A grasshopper is sitting on the number line. Initially, it is sitting at the number 0 . Each second it jumps one unit to the left or to the right, with equal probability. The directions of the jumps are chosen independently of each other.

Let $p$ denote the probability that, after 2022 jumps, the grasshopper is sitting at a number divisible by 5 . Determine whether $p\frac{1}{5}$.
Solution via a recurrence relation
For $n \geq 0$ let
$a_{n}=$ the probability that the grasshopper sits in $5 \mathbb{Z}$ after $n$ jumps,
$b_{n}=$ the probability that the grasshopper sits in $5 \mathbb{Z}+1$ after $n$ jumps
$c_{n}=$ the probability that the grasshopper sits in $5 \mathbb{Z}+2$ after $n$ jumps
$d_{n}=$ the probability that the grasshopper sits in $5 \mathbb{Z}+3$ after $n$ jumps
$e_{n}=$ the probability that the grasshopper sits in $5 \mathbb{Z}+4$ after $n$ jumps.

Then, for all $n \geq 0$,
$$
\begin{array}{l}
a_{n+1}=\frac{1}{2} b_{n}+\frac{1}{2} e_{n} \\
b_{n+1}=\frac{1}{2} a_{n}+\frac{1}{2} c_{n} \\
c_{n+1}=\frac{1}{2} b_{n}+\frac{1}{2} d_{n} \\
d_{n+1}=\frac{1}{2} c_{n}+\frac{1}{2} e_{n} \\
e_{n+1}=\frac{1}{2} d_{n}+\frac{1}{2} a_{n} .
\end{array}
$$

We also have $a_{0}=1 ; b_{0}=c_{0}=d_{0}=e_{0}=0$ and $a_{1}=0 ; b_{1}=\frac{1}{2} ; c_{1}=0 ; d_{1}=0 ; e_{1}=\frac{1}{2}$ We claim that $b_{n}=e_{n}$ and $c_{n}=d_{n}$ for all $n \geq 0$. This is readily proved by induction, but also follows from a symmetry argument. Since the grasshopper jumps left or right with equal probabilities, the probability that it is sitting at the integer $k$ after $n$ jumps is equal . As sets we have $(5 \mathbb{Z}+1)=-(5 \mathbb{Z}+4)$ and $(5 \mathbb{Z}+2)=-(5 \mathbb{Z}+3)$, from which the claim follows. It follows that
$$
\begin{array}{l}
a_{n+1}=b_{n} \\
b_{n+1}=\frac{1}{2} a_{n}+\frac{1}{2} c_{n} \\
c_{n+1}=\frac{1}{2} b_{n}+\frac{1}{2} c_{n},
\end{array}
$$
for all $n \geq 0$
We now present two ways to finish the problem from here. For the first, we will show that $p>\frac{1}{5}$ without explicitly solving the recurrence relation, by proving by induction that $a_{n}>c_{n}>b_{n}$ for all even $n>0$. In the base case $n=2$ we have $a_{2}=\frac{1}{2}, c_{2}=\frac{1}{4}$ and $b_{2}=0$, so the claim holds. For the inductive step we use the relations above to obtain
$$
\begin{aligned}
a_{n+2} & =\frac{1}{2} a_{n}+\frac{1}{2} c_{n}, \\
b_{n+2} & =\frac{3}{4} b_{n}+\frac{1}{4} c_{n}, \\
c_{n+2} & =\frac{1}{4} a_{n}+\frac{1}{4} b_{n}+\frac{1}{2} c_{n},
\end{aligned}
$$
for all $n \geq 0$. Supposing now that $a_{n}>c_{n}>b_{n}$ for some $n \geq 0$ we have
$$
\begin{array}{l}
a_{n+2}-c_{n+2}=\frac{1}{4}\left(a_{n}-b_{n}\right)>0, \\
c_{n+2}-b_{n+2}=\frac{1}{4}\left(a_{n}-b_{n}\right)+\frac{1}{4}\left(c_{n}-b_{n}\right)>0,
\end{array}
$$
completing the inductive step. To finish the problem we observe that for all even $n>0$ since $a_{n}, b_{n}, c_{n}, d_{n}, e_{n}$ sum to 1 and are not all equal the largest, namely $a_{n}$, must be strictly greater than the average $\frac{1}{5}$
For the second approach we will use the relations above to obtain an explicit formula for $a_{n}$. Combining the three relations we find that, for $n \geq 2$,
$$
\begin{aligned}
a_{n+1} & =\frac{1}{2}\left(a_{n-1}+c_{n-1}\right) \\
& =\frac{1}{2}\left(a_{n-1}+\frac{1}{2}\left(b_{n-2}+c_{n-2}\right)\right) \\
& =\frac{1}{2}\left(a_{n-1}+\frac{1}{2} b_{n-2}+b_{n-1}-\frac{1}{2} a_{n-2}\right) \\
& =\frac{1}{2}\left(a_{n-1}+\frac{1}{2} a_{n-1}+a_{n}-\frac{1}{2} a_{n-2}\right) \\
& =\frac{1}{2} a_{n}+\frac{3}{4} a_{n-1}-\frac{1}{4} a_{n-2} .
\end{aligned}
$$

The characteristic equation of this recurrence relation is $x^{3}-\frac{1}{2} x^{2}-\frac{3}{4} x+\frac{1}{4}=0$. An obvious root is $x=1$, and the other two roots follow easily: $x=\frac{1}{4}(-1 \pm \sqrt{5})$. So ther exist constants $A, B, C$ such that $a_{n}=A+B\left(\frac{1}{4}(-1+\sqrt{5})\right)^{n}+C\left(\frac{1}{4}(-1-\sqrt{5})\right)^{n}$ for all $n \geq 0$. Using $a_{0}=1, a_{1}=0, a_{2}=\frac{1}{2}$, we easily find the values of these constants. $n \geq 0$. Using $a_{0}=1, a_{1}=0, a_{2}=\frac{1}{2}$, we easily $A=\frac{1}{5}, C=\frac{2}{5}$. Consequently, for all $n \geq 0$,
$$
a_{n}=\frac{1}{5}+\frac{2}{5}\left[\left(\frac{1}{4}\right)^{n}\left((-1+\sqrt{5})^{n}+(-1-\sqrt{5})^{n}\right)\right] .
$$

Since the expression between the square brackets is positive for even $n$, it follows that $a_{n}>\frac{1}{5}$ if $n$ is even. In particular, $p=a_{2022}>\frac{1}{5}$.

Solution via a generating function
For each integer $k$ and nonnegative integer $n$ let $g_{n}(k)$ be the probability that the grasshopper is sitting at the number $k$ after $n$ jumps, and let
$$
G_{n}(x)=\sum_{k \in \mathbb{Z}} g_{n}(k) x^{k}
$$
be the generating function of the sequence $\left(g_{n}(k)\right)_{k \in \mathbb{Z}}$. For all $n \geq 0$ and all $k \in \mathbb{Z}$ we have
and it follows that
$$
g_{n+1}(k)=\frac{g_{n}(k-1)+g_{n}(k+1)}{2},
$$

Since $G_{0}(x)=1$ we obtain
$$
\begin{aligned}
G_{n+1}(x) & =\frac{1}{2}\left(x+x^{-1}\right) G_{n}(x) . \\
G_{n}(x) & =\left(\frac{x+x^{-1}}{2}\right)^{n} .
\end{aligned}
$$

Note that $G_{n}$ is a polynomial in $x$ and $x^{-1}$ for all $n$
We are interested in the sum $p=\sum_{k \in 5 \mathbb{Z}} g_{2022}(k)$. More generally let $p_{n}=\sum_{k \in 5 \mathbb{Z}} g_{n}(k)$, and let $\zeta=e^{2 \pi i / 5}$ be a fifth root of unity. We claim that
$$
\sum_{j=0}^{4} G_{n}\left(\zeta^{j}\right)=5 p_{n}
$$

Indeed,
$$
\begin{aligned}
\sum_{j=0}^{4} G_{n}\left(\zeta^{j}\right) & =\sum_{j=0}^{4} \sum_{k \in \mathbb{Z}} g_{n}(k) \zeta^{j k} \\
& =\sum_{k \in \mathbb{Z}} g_{n}(k) \sum_{j=0}^{4} \zeta^{j k} .
\end{aligned}
$$

If $k \in 5 \mathbb{Z}$ then $\zeta^{j k}=1$ for all $j$, and otherwise $\zeta^{0}, \zeta^{k}, \zeta^{2 k}, \zeta^{3 k}, \zeta^{4 k}$ are equal to $1, \zeta^{1}, \zeta^{2}, \zeta^{3}, \zeta^{4}$ Now
$$
\begin{array}{c}
G_{n}(1)=1, \\
G_{n}(\zeta)=G_{n}\left(\zeta^{4}\right)=\cos ^{n} \frac{2 \pi}{5}, \\
G_{n}\left(\zeta^{2}\right)=G_{n}\left(\zeta^{3}\right)=\cos ^{n} \frac{4 \pi}{5}, \\
p_{n}=\frac{1}{5}\left(1+2 \cos ^{n} \frac{2 \pi}{5}+2 \cos ^{n} \frac{4 \pi}{5}\right) .
\end{array}
$$
so

Finally when $n=2 m$ is even we have
$$
5 p_{n}=1+2\left(\cos ^{m} \frac{2 \pi}{5}\right)^{2}+2\left(\cos ^{m} \frac{4 \pi}{5}\right)^{2}>1,
$$
so $p=p_{2022}>\frac{1}{5}$.
Comment
Using the triangle below it can be shown that the length $r$ satisfies $r^{2}+r-1=0$, so that $r=\frac{-1+\sqrt{5}}{2}$. Then
$$
\begin{array}{l}
\cos \frac{2 \pi}{5}=\frac{r}{2}=\frac{-1+\sqrt{5}}{4}, \\
\cos \frac{4 \pi}{5}=1-2 \cos ^{2} \frac{2 \pi}{5}=\frac{-1-\sqrt{5}}{4},
\end{array}
$$
so our expression for $p_{n}$ agrees with our expression for $a_{n}$, as it should.