# 1991 IMO shortlist problem $\#11$

Prove that $$\sum_{k=0}^{995} \frac{(-1)^k}{1991-k} {1991-k\choose k} = \frac{1}{1991}$$

As usual there isn't anything special about the number $$1991$$.Problem appears to hold for any odd numbers I have checked. I want to prove the general equation. We can manipulate expression and simplify a bit. Then the problem reduces to showing that $$\sum_{k=1}^{n} \frac{(-1)^k}{2n-2k+1} {2n-k\choose k} = 0$$ for some positive integer $$n$$. This is the equation I had been working on but it wasn't that fruitful.

I gave up and saw the solution on Aops but it was not a elementary one. Here is the link if any one wants to see it "https://artofproblemsolving.com/community/c6h34892p216919" ( There is another interesting thing about this link, that the last six digits form a prime number!! $$216919$$ ).In this link the solution poster says that the solution he had written isn't the solution the creators assumed the students to write. So what might be the solution that creators might have expected the students to write?

• What do you think about the $995$? Have you played with that number at all? – Michael Morrow Sep 22 '20 at 18:25
• Its $\lfloor \frac {1991}{2} \rfloor$. I Have taken it into account to come up with generalised statement. – Mathematical Curiosity Sep 22 '20 at 18:28
• Gotcha. Yeah, it looks like there should be a way to relate this to a counting problem.. – Michael Morrow Sep 22 '20 at 18:30
• Yes, that's most likely the case. But coming up with a combinatorial proof is very hard. Do you have any ideas? – Mathematical Curiosity Sep 22 '20 at 18:33
• Alternative signs suggest PIE. – cosmo5 Sep 22 '20 at 18:43

For such problems (esp when you notice that there is a general pattern), some ideas are to find a recurrence relation, create something telescoping (or treat it as a generating function).

We'd use these ideas here.

Notice that $$\left(\frac{1}{n-m} - \frac{1}{n}\right) { n - m \choose m } = \frac{m}{ n (n-m) } { n - m \choose m } = \frac{1}{n} {n-m-1 \choose m-1}$$, or that

$$\frac{ 1 } { n-m } { n-m \choose m } = \frac{1}{n} \left[ { n - m \choose m } + { n - m - 1 \choose m- 1 } \right].$$

This is a good substitution, as it gets rid of the pesky $$\frac{1}{n-k}$$ which makes recurrence hard, and also gives us a $$\frac{1}{1991}$$ on the RHS.

Thus, the goal is to determine $$\sum_{k=0}^{995 } (-1)^k \left[ {1991-k\choose k} + { 1991 - k - 1 \choose k - 1 } \right]$$. (We will show that it equals to 1, and thus the desired sum is $$\frac{1}{1991}.$$)

Let $$S_n = \sum_{k=0}^{ \lfloor \frac{n}{2} \rfloor} (-1)^k { n-k \choose k }$$.

Notice that $${n-k \choose k } = { n-k - 1 \choose k } + { n-k - 1 \choose k - 1 }$$, so

$$S_n = \sum_{k=0}^{\lfloor \frac{n+1}{2} \rfloor} (-1)^k { n - k + 1 \choose k } \\ = \sum_{k=0}^{\lfloor \frac{n+1}{2} \rfloor} (-1)^k \left[ {n-k \choose k } + {n-k \choose k - 1 } \right] \\ = \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} (-1)^k {n-k \choose k } + \sum_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} (-1)^k { n-k \choose k } \\ = S_{n} - S_{n-1}.$$

(Take care in checking the indices, and remember those $${n \choose m } = 0$$ when $$m > n$$.)

Using this recurrence relation, and calculating some initial values, we get $$S_n = 1 , 0, -1, -1, 0, 1, 1, 0, -1, \ldots$$, which has period 6.
We thus want to determine $$S_{1991} - S_{1990} = 0 - (-1) = 1$$.

Notes

1. I do wish there was a combinatorial argument here. For example, $$S_n$$ has an immediate interpretation as the difference between the even and odd permutations $$p$$ such that $$|p(i) - i | \leq 1$$. (IE Out of the first $$n$$ integers, there are $${n-k \choose k }$$ ways to pick k pairs of consecutive integers (for a total of 2k). The perumatation which switches these pairs and keep the rest fixed has parity $$k$$.) However, I don't see an obvious way to show that this difference is $$1, 0, -1, -1, 0, 1, \ldots$$.

2. WhatsUp's conclusion that about the value of $$s_n$$ also follows from the above.

If you know generating functions, then here is a solution:

Let $$s_n$$ denote the sum $$\sum_{k \geq 0} \frac{(-1)^k}{n - k}\binom{n - k}k$$ and let $$S(X)$$ be the formal power series $$S(X) = \sum_{n \geq 1} s_n X^n$$.

We compute:

$$\begin{eqnarray} S(X) &=& \sum_{n \geq 1} \frac 1 n X^n + \sum_{n \geq 1}\sum_{k \geq 1} \frac{(-1)^k}{n - k}\binom{n - k}k X^n\\ &=& -\log(1 - X) + \sum_{k \geq 1}\sum_{n \geq 2k}\frac{(-1)^k}k \binom{n - k - 1}{k - 1}X^n\\ &=& -\log(1 - X) + \sum_{k \geq 1}\frac{(-1)^k}k X^{2k}\sum_{n \geq 0}\binom{n + k - 1}{k - 1}X^n\\ &=& -\log(1 - X) - \sum_{k \geq 1}\frac{ (-1)^{k - 1}} k \left(\frac{X^2}{1 - X}\right)^k\\ &=& -\log(1 - X) - \log\left(1 + \frac{X^2}{1 - X}\right)\\ &=& -\log(1 - X + X^2)\\ &=& -\log(1 - \omega X) - \log(1 - \overline\omega X)\\ &=& \sum_{n \geq 1}\frac{\omega^n + \overline\omega^n}n X^n, \end{eqnarray}$$ where $$\omega = \frac{1 + \sqrt{-3}}2$$ is a primitive sixth root of unity.

Thus we have $$s_n = \frac 1 n \cdot 2 \operatorname{Re}(\omega^n)$$.

Now $$\omega^n$$ only depends on $$n \mod 6$$. Therefore: $$s_n = \begin{cases} \frac 2 n, & n \equiv 0\mod 6;\\ \frac 1 n, & n \equiv 1, 5\mod 6;\\ \frac {-1} n, & n \equiv 2, 4 \mod 6;\\ \frac{-2} n, & n \equiv 3 \mod 6. \end{cases}$$

And the answer to the original question follows from the fact that $$1991 \equiv 5 \mod 6$$.

• Thanks for your solution. But I don't know much of generating functions. Isn't there any other solutions? – Mathematical Curiosity Sep 23 '20 at 5:58
• I think it's the most natural solution to this problem. Other solutions, if exist, would be complicated, as can be seen from the answer. You may consider learning generating functions, as it's a powerful tool that is accessible to high school students. – WhatsUp Sep 23 '20 at 8:53
• Can you suggest a good source for learning it? – Mathematical Curiosity Sep 23 '20 at 10:34
• I would suggest starting with the wiki pages on (ordinary) generating functions and formal power series, googling introductory materials on the subject, and looking at some motivating examples such as this problem. – WhatsUp Sep 23 '20 at 12:48
• Thank you very much! – Mathematical Curiosity Sep 23 '20 at 14:17