Prove that $ \sum_{k = 0}^{995} \frac {( - 1)^k}{1991 - k} {1991 - k \choose k} = \frac {1}{1991}$
Problem
Source: IMO ShortList 1991, Problem 11 (AUS 4)
Tags: combinatorics, series summation, binomial coefficients, Summation, Combinatorial Identity, IMO Shortlist
05.05.2005 13:45
We can rewrite it as $S=\sum_{k = 1}^{n/2} \frac{(-1)^k}{k} {n-k \choose k-1} = 0$, where $n=1990$. Using identity $\binom{n-k}{k-1}=\binom{n-k}{n-2k+1}$, we see that \[S=\mathop{coef}_{u^{-1}}\sum_{k=1}^{n/2}\frac{(-1)^k}{k}(1+u)^{n-k}u^{-n+2k-2}=\] \[=\mathop{coef}_{u^{-1}}\frac{(1+u)^n}{u^{n+2}}\sum_{k=1}^{\infty}\frac{(-1)^k}{k}\left(\frac{u^2}{1+u}\right)^k=\mathop{coef}_{u^{-1}}\frac{(1+u)^n}{u^{n+2}}\ln\left(1+\frac{u^2}{1+u}\right)=\] \[=\mathop{Res}_{u=0}\frac{(1+u)^n}{u^{n+2}}\ln\left(1+\frac{u^2}{1+u}\right).\] See http://www.mathlinks.ro/Forum/viewtopic.php?t=35810 for a continuation. Though I don't think that ISL assumed such an approach, Peter.
05.05.2005 18:25
forgive me for asking, 'cause i don't know, but what does Res refer to? hey, and thanks for responding, Myth. i think you're right, the proposers probably didn't have a solution like this in mind. i haven't really worked on the problem yet, but it seems to me like it should have a combinatorial interpretation, probably having to do with inclusion-exclusion and probabilities.
08.05.2005 10:35
Res stands for residue, e.g, the coefficient of $z^{-1}$ of the laurent series of $f(z)$
31.07.2014 17:43
So does someone have a combinatorial proof ????
12.04.2018 23:36
Maybe we can use limit theorem
23.11.2021 17:16
Let $S$ denote the sum then after some simplifications, I got \[S=\sum_{k=0}^{995} (-1)^k \cdot \frac{(k+1)(k+2)\cdots (1989-2k)}{1991-2k}\] Can anyone help me for further?
10.02.2022 09:12
So there's no one have combinatorial proofs?
15.07.2024 13:32
Bumping this in hopes of getting a combinatorial arguement.