1991 IMO shortlist problem $#11$

Question

PROBLEM : Prove that $sum_{k=0}^{995} frac{(-1)^k}{1991-k} {1991-kchoose 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-kchoose 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?

Calvin Lin · Accepted Answer

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-kchoose 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

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 $.

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

WhatsUp · 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) - logleft(1 + frac{X^2}{1 - X}right)\
&=& -log(1 - X + X^2)\
&=& -log(1 - omega X) - log(1 - overlineomega X)\
&=& sum_{n geq 1}frac{omega^n + overlineomega^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 0mod 6;\
frac 1 n, & n equiv 1, 5mod 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$.

1991 IMO shortlist problem $#11$

2 Answers

Add your own answers!

Ask a Question