# 1991 IMO shortlist problem $#11$

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?

Mathematics Asked by Mathematical Curiosity on January 1, 2021

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

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.

Correct answer by Calvin Lin on January 1, 2021

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

Answered by WhatsUp on January 1, 2021

## Related Questions

### Solving a simple differential equation with DFT

1  Asked on November 1, 2021 by gaganov-victor

### How do I use structural induction to show that for all $(a,b) in S$ that $(a+b) = 4k$ for some $k in Bbb Z$?

1  Asked on November 1, 2021 by justanotherstudent

### Initial value problem $xyz_x + x^2z_y = x^2+y^2-yz$ with initial curve

1  Asked on November 1, 2021 by briemann

### Simplify $sum^{20}_{k=10} kbinom{k-1}{9}$.

3  Asked on November 1, 2021

### Conjugate in $S_n$ do not imply conjugate in its subgroup.

3  Asked on November 1, 2021

### Cardinality of set of $a_r$?

1  Asked on November 1, 2021

### Learn how to sketch functions intuitively

3  Asked on November 1, 2021 by q0mlm

### Definition of addition and multiplication on $ℕ$ using recursion

2  Asked on November 1, 2021

### Acceleration of a particle varies with distance as $-kx$. The particle is initially given a velocity $v_0$. Find time take to reach initial point

1  Asked on November 1, 2021

### Vector notation for $k>n$ vectors in $Bbb{R^n}$

1  Asked on November 1, 2021

### Matrix determinant with complex coefficients

1  Asked on November 1, 2021

### How do you mathematically define a random line or in general, a random subspace of a Euclidean space?

2  Asked on November 1, 2021

### Why do Fresnel-integrals contain $sqrt{pi}$?

0  Asked on November 1, 2021 by rickard-martensson

### Solve the differential equation $(D^3-3D^2+4D-2)y = (e^x +cos x)$, where $D = frac{mathrm{d}}{mathrm{d}x}$.

2  Asked on November 1, 2021 by piyush-mahajan

### Prove that the following sequence $(sinfrac{pi k}{3})_{k=1}^infty$ diverges

1  Asked on November 1, 2021 by ovunc

### A question on linear maps itself

3  Asked on March 16, 2021 by popping900

### $f$ is convex and $f(10)$, $f(20)$ given. Find the smallest value of $f(7)$.

2  Asked on March 15, 2021 by jixubi

### Linearize product of Two Special Ordered Sets and minimize number of variables

1  Asked on March 13, 2021 by kamer73

### Given 6 distinct points in $3$-$D$ space, can the distances between $3$ of the points be determined if all other distances between points are known?

1  Asked on March 10, 2021 by apoapsis

### How to find the generators of a principal Ideal?

1  Asked on March 10, 2021 by ayoub-rossi