# Find the number of series

Find the number of series $(a_1,..., a_{2n})$ that have terms from ${\{0,...9\}}$ so that:

$$11|\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i$$

(this is not a homework)

There is a similar problem (Problem 6) in the IMO 1995.

• Whatever it is, HW or not, one would expect you show some self effort, some work, some ideas on what's going on here... – DonAntonio Mar 25 '14 at 13:54
• $(0,....,0)$ or $a_{i}=0$ is a solution since $11|0$ is true. – Danny Mar 25 '14 at 14:03
• Consider $1+z+...+z^9$ If we put $(1+z+...+z^9)^n$ the coefficient of $z^k$ in its expansion will be the number of ways to write $k$ as a sum of $n$ numbers from $\{0,...,9\}$. Similarly, in $f(z)=(1+z+...+z^9)^n(1+z^{-1}+...+z^{-9})^n$ the coefficient of $z^k$ is the number of ways to write $k$ as $\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i$, with $a_i\in\{0,...,9\}$. Now we only need to remove from there the terms with exponents that are not multiples of $11$, consider $w=e^{2\pi i/11}$. Recall that $1+w+...+w^{10}=0$, and $w^{11}=1$. Then $(f(z)+f(wz)+...+f(w^{10})/11$ ... – OR. Mar 25 '14 at 14:33
• has the terms of $f$ with exponents divisible by $11$. Finally, since we want to count all possible series for all possible sum divisible by $11$ we can take $(f(z)+f(wz)+f(w^2z)+...+f(w^{10}z))/11$ and evaluate it at $z=1$. – OR. Mar 25 '14 at 14:37
• Now notice that we can simplify $f$. We have$f(z)=\left(\frac{z^{10}-1}{z-1}\right)^n\left(\frac{z^{0}-z^{10}}{z^{9}-z^{10}}\right)^n$ – OR. Mar 25 '14 at 14:43

For a fixed $n$, let $A_r$ be the number of sequences of $n$ terms, whose sum is $r \pmod{11}$. Then, we want the value of $\sum A_r ^2$.

As pointed out by ABC, the generating function $f(x) = \left ( 1 + x + x^2 + \ldots + x^9 \right) ^n$ gives us the number of sequences of $n$ terms, with a total sum of $r$. We find the sum of those coefficients with the power mod 11, we use the typical counting trick. Let $\omega$ be a primitive 11th root of unity. We know that $1 + \omega + \omega^2 + \ldots + \omega^{10} = 0$. For $i \not \equiv 0 \pmod{11}$, we have $f( \omega^i) = ( -\omega^{10i})^n$

We have $$11 A_r = \sum_{i=0}^{10} \omega^{-ri} f( \omega^i) = 10^n + \sum_{i=1}^{10} \omega^{-ri} (- \omega^{10i})^n = 10^n + (-1)^n \sum_{i=1}^{10} \omega^{(10n-r)i}.$$

In particular, this shows that for $r \neq 10n \pmod{11}$, we have $A_r = \frac{10^n-(-1)^{n}}{11}$. Otherwise, for $R \equiv 10n \equiv -n \pmod{11}$, we have $A_R = \frac{10^n+10 \times (-1)^n}{11}$.

Hence, we can now find the sum as

$$\sum_{r=0}^{10} A_r^2 = 10 \left (\frac{10^n-(-1)^n}{11} \right)^2 + \left( \frac{10^n+10\times (-1)^n}{11} \right)^2$$

Note: This solution is nice 9 because 2 less than 11, which makes $f(\omega^i)$ easy to evaluate. For a much more general case, the equations would not be pretty.

• There is a wait of 14 hours until you get your bounty. – OR. Mar 28 '14 at 0:08
• Why the down vote? – Calvin Lin Mar 29 '14 at 19:22
• Could it be that you made a small mistake when replacing $(-\omega^{10i})^n$ by $-\omega^{10in}$ or is there something else you did? If so, there would be different answers depending on the parity of $n$, namely $10\left(\frac{10^n+1}{11}\right)^2+\left(\frac{10^n-10}{11}\right)^2$ for odd $n$ and $10\left(\frac{10^n-1}{11}\right)^2+\left(\frac{10^n+10}{11}\right)^2$ for even $n$, right? I suppose so, because the result you got for $A_r$ is not integer for even $n$, as $10^{2m}\equiv1\pmod{11}$. But apart from this, nice solution! It took me some time to understand but I learned much from it! – punctured dusk Apr 4 '14 at 13:00
• @barto Yes indeed! Updated. $A_r$ wouldn't have been an integer in certain cases. – Calvin Lin Apr 4 '14 at 20:38

Since the second term is larger than the first term

-Sum = (2n * (2n+1))/2 - 2*(n*(n+1))/2 = n*(2n+1) -n*(n+1) =n*n

(Sorry not used to site so plain english).

So 11 divides the series iff 11 divides n.