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?
Best Answer
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$.