Problem source

A 6-sided fair die has the numbers 1,  2, 3, 4, 5, 6  on its faces. The die is  thrown $n$ times, the outcome (the number on the top face) of each throw being independent of the outcome of any other throw. The random variable $S_n$
 is the sum of the outcomes.
\begin{questionparts}
\item The random variable~$R_n$ is the remainder when $S_n$ is divided by 6. Write down the probability generating function, $\G(x)$, of $R_1$ and show that the probability generating function of $R_2$ is also $\G(x)$. Use a generating function to find the probability that $S_n$ is divisible by 6.
\item The random variable $T_n$ is  the remainder when $S_n$ is divided by 5. Write down the probability generating function, $\G_1(x)$, of $T_1$ and show that $\G_2(x)$, the probability generating function of $T_2$, is given by 
\[
{\rm G}_2(x) = \tfrac 1 {36} (x^2 +7y) 
\]
where $y= 1+x+x^2+x^3+x^4\,$.
Obtain the probability generating function of  $T_n$ and hence show that the probability that $S_n$ is divisible by $5$ is 
\[
\frac15\left(1- \frac1 {6^n}\right)
\]
if $n$ is not divisible by 5. What is the corresponding probability if $n$ is divisible by 5?
\end{questionparts}

Solution source

\begin{questionparts}
\item $G(x) = \frac{1}{6} (1 + x + x^2 + x^3 + x^4 + x^5)$

The pgf for $R_2$ is:

\begin{align*}
\frac1{36}x^2 + \frac{2}{36}x^3 + \frac{3}{36}x^4 + \frac{4}{36}x^5 + \frac{5}{36} +\\
\quad \quad + \frac{6}{36}x^1 + \frac{5}{36}x^2 + \frac4{36}x^3 + \frac3{36}x^4 + \frac{2}{36}x^5 + \frac{1}{36} \\
= \frac{1}{6}(1 + x + x^2 + x^3 + x^4 + x^5) = G(x)
\end{align*}

Since rolling the dice twice is the same as rolling the dice once, rolling the dice $n$ times will be the same as rolling it once, ie the pgf for $R_n$ will be $G(x)$ and the probability $S_n$ is divisible by $6$ is $\frac16$

\item $G_1(x) = \frac{1}{6} + \frac{1}{3}x^1 + \frac{1}{6}x^2 + \frac16x^3+ \frac16x^4 = \frac16(1 + 2x+x^2+x^3+x^4)$.

If $G_n$ is the probability generating function for $T_n$ then we can obtain $G_n$ by multiplying $G_{n-1}$ by $G(x)$ and replacing any terms of order higher than $5$ with their remainder on division by $5$. (Or equivalently, working over $\mathbb{R}[x]/(x^5-1)$.  If $y = 1 + x + x^2 + x^3 + x^4$ then:
\begin{align*}
xy &= x + x^2 + x^3 + x^4 +x^5 \\
&=  x + x^2 + x^3 + x^4 + 1 \\
&= y \\
\\
y^2 &= (1 + x+x^2 + x^3+x^4)^2 \\
&= 1 + 2x + 3x^2 + 4x^3+5x^4+4x^5+3x^6 + 2x^7 + x^8 \\
&= (1+4) + (2+3)x+(3+2)x^2 + (4+1)x^3 + 5x^4 \\
&= 5y
\end{align*}

\begin{align*}
\frac{1}{36}(y+x)(y+x) &= \frac1{36}(y^2 + 2xy + x^2) \\
&= \frac1{36}(5y + 2y + x^2 ) \\
&= \frac1{36}(7y + x^2)
\end{align*}

Similarly,

\begin{align*}
G_n(x) &= \l\frac{1}{6}(x+y) \r^n \\
&= \frac1{6^n} \l \sum_{i=0}^n \binom{n}{i} y^ix^{n-i} \r \\
&= \frac1{6^n} \l \sum_{i=1}^n \binom{n}{i} y^i + x^n \r \\
&= \frac1{6^n} \l \sum_{i=1}^n \binom{n}{i} 5^{i-1}y + x^n \r \\
&= \frac1{6^n} \l \frac{1}{5}y((5+1)^n-1) + x^n \r \\
&= \frac1{6^n} \l \frac{1}{5}y(6^n-1) + x^n \r \\
\end{align*}

Therefore if $n \not \equiv 0 \pmod{5}$, we can find the probability of $T_n = 0$ by looking at the constant coefficient, ie plugging in $x = 0$, which is:

\[\frac1{6^n} \l \frac{1}{5}(6^n-1) \r = \frac{1}{5} \l 1- \frac{1}{6^n}   \r \] 

When $n \equiv 0 \pmod{5}$ we can also find the constant coefficient by plugging in $x = 0$, which is:

\[\frac1{6^n} \l \frac{1}{5}(6^n-1) + 1 \r = \frac{1}{5} \l 1+ \frac{4}{6^n}   \r \] 

\end{questionparts}

Note: this whole question can be considered a "roots-of-unity" filter in disguise. Our computations in $\mathbb{R}[x]/(x^5 - 1)$ are the same as computations using $\omega$, in fact $\mathbb{R}[x]/(x^5 - 1) \cong \mathbb{R}[\omega]$ where $\omega$ is a primitive $5$th root of unity