(Feller Vol.1, P.285, Q.21) Let $u_n$ be the probability that the number of successes in $n$ Bernoulli trials is divisible by $3$. Find a recursive relation for $u_n$. Answer: $u_n = q^n + \sum_{k=3}^n {k-1 \choose 2} p^3 q^{k-3} u_{n-k}$ with $u_0 = 1, u_1=q, u_2 = q^2, u_3 = p^3 + q^3$.
I understand that $q^n$ represents ${n \choose 0}p^0q^n$, but I don't know how to interpret the series. I tested the answer for the case of $u_6$. $u_6 = q^6 + {6 \choose 3} p^3q^3 + {6 \choose 6} p^6q^0$, and I checked that the answer works. However, I cannot do more than that. I would appreciate if you explain how to derive the answer.
Suppose the number of successes in $n$ trials is divisible by $3$. Then, either there are no successes at all (the first term) or there are $3m$ successes for some $m>0$.
Assume that we are in the second case. Then let $k$ be the location of the the third success. There are, of course, $n-k$ trials left to go. The probability that $k$ is the third success and the number of successes in the remaining $n-k$ trials is a multiple of $3$ is given by $$\binom {k-1}2p^3q^{k-3}u_{n-k}$$
hence the summands.