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

2 AnswersFor 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.

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

1 Asked on November 1, 2021 by gaganov-victor

fast fourier transform numerical methods ordinary differential equations

1 Asked on November 1, 2021 by justanotherstudent

discrete mathematics divisibility elementary number theory induction

1 Asked on November 1, 2021 by briemann

3 Asked on November 1, 2021

3 Asked on November 1, 2021

1 Asked on November 1, 2021

3 Asked on November 1, 2021 by q0mlm

2 Asked on November 1, 2021

1 Asked on November 1, 2021

1 Asked on November 1, 2021

2 Asked on November 1, 2021

geometric probability probability probability distributions random graphs random matrices

0 Asked on November 1, 2021 by rickard-martensson

fresnel integrals integration transcendental equations transcendental functions

2 Asked on November 1, 2021 by piyush-mahajan

calculus differential operators ordinary differential equations

1 Asked on November 1, 2021 by ovunc

convergence divergence epsilon delta limits real analysis solution verification

3 Asked on March 16, 2021 by popping900

2 Asked on March 15, 2021 by jixubi

1 Asked on March 13, 2021 by kamer73

1 Asked on March 10, 2021 by apoapsis

1 Asked on March 10, 2021 by ayoub-rossi

Get help from others!

Recent Answers

- kjetil b halvorsen on How to test consistency of responses?
- eric_kernfeld on How to test consistency of responses?
- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- Philipp on How do i draw a ray in unity

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

© 2022 AnswerBun.com. All rights reserved.