# Show that $\lim_{n\to \infty} \dfrac{c_n}{k^n} = \dfrac{1}{p}$

Let $p$ be an odd prime and let $a_1,a_2,\ldots,a_k$ be integers not all equivalent modulo $p$. For each $n>0$, let $c_n$ denote the number of tuples $(b_1,b_2,\ldots,b_n)$ with $1\le b_i \le k$ for each $i$ such that $p|a_{b_1}+a_{b_2}+\cdots+a_{b_n}$. Show that $\displaystyle\lim_{n\to \infty} \dfrac{c_n}{k^n} = \dfrac{1}{p}$.

I thought about using complex numbers here. It seems hard to count the number of tuples directly, so is there a way we can in order to calculate the limit? A roots of unity filter with $\zeta = g^{2n}$ where $g$ is a primitive root modulo $n$ gives $$\frac{(1 + \zeta^0 x)^{nk} + (1 + \zeta^1 x)^{nk} + \cdots + (1 + \zeta^{k-1} x)^{nk}}{k} \equiv 1+x^k+x^{2k}+\cdots +x^{nk} \pmod{p},$$ but I wasn't sure if this helps.

Define $f(x)=\sum x^{a_j}$.

If $g_n(x)=f(x)^n$, then $c_n$ is the sum of the coefficients if $g_n(x)$ with exponents divisible by $p$.

That means $$c_n=\frac{1}{p}\sum_{i=0}^{p-1} g_n(\zeta^i)$$ where $\zeta$ is a primitive $p$th root of $1$.

Then:

$$\frac{c_n}{k^n}=\frac{1}{p}\sum_{i=0}^{p-1} \left(\frac{f(\zeta^i)}{k}\right)^n$$

Now, when $i\neq 0$, $\left|\frac{f(\zeta^i)}k\right|<1$ because it is the center of mass of $k$ points on the unit circle, not all equal.

So if $i=1,\dots,p-1$ then $\frac{f(\zeta^i)}{k}\to 0$.

Also, $\frac{f(1)}{k}=1$.

Thus $\frac{c_n}{k^n}\to \frac{1}{p}$.

You can likely put together a Markov chain argument, but I'm having a hard time figuring it.

• What if all the $a_i$ are equivalent modulo $p$? – user19405892 Dec 28 '16 at 0:54
• Then $\frac{f(\zeta^i)}{k}=\zeta^{ia_1}$. But basically, then $c_n=1$ if $p\mid n$ or if all $a_i\equiv 0\pmod p$, otherwise $c_n=0$. – Thomas Andrews Dec 28 '16 at 1:01
• So that is a necessary condition? – user19405892 Dec 28 '16 at 1:02
• Sorry, $c_n=k^n$ if $p\mid n$ or if all $a_i\equiv 0$. And yes, the condition is necessary. – Thomas Andrews Dec 28 '16 at 1:03
• Where did you use the condition in the solution and also that $p$ is odd? – user19405892 Dec 28 '16 at 1:07