Problem z krótką listą IMO 1991 $\#11$
Udowodnij to $$\sum_{k=0}^{995} \frac{(-1)^k}{1991-k} {1991-k\choose k} = \frac{1}{1991}$$
Jak zwykle nie ma w tej liczbie nic specjalnego $1991$Wydaje się, że problem utrzymuje się dla wszystkich sprawdzonych liczb nieparzystych. Chcę udowodnić ogólne równanie. Możemy manipulować ekspresją i trochę uprościć. Wtedy problem sprowadza się do pokazania tego$\sum_{k=1}^{n} \frac{(-1)^k}{2n-2k+1} {2n-k\choose k} = 0$ dla jakiejś dodatniej liczby całkowitej $n$. To jest równanie, nad którym pracowałem, ale nie było tak owocne.
Poddałem się i zobaczyłem rozwiązanie na Aops, ale nie było to elementarne. Oto link, jeśli ktoś chce go zobaczyć "https://artofproblemsolving.com/community/c6h34892p216919" (Jest jeszcze jedna interesująca rzecz w tym łączu, że ostatnie sześć cyfr tworzy liczbę pierwszą !!$216919$W tym linku plakat rozwiązania mówi, że napisane przez niego rozwiązanie nie jest rozwiązaniem, które twórcy założyli, że napisali uczniowie. Jakie więc może być rozwiązanie, którego twórcy mogli oczekiwać od uczniów?
Odpowiedzi
W przypadku takich problemów (szczególnie, gdy zauważysz, że istnieje ogólny wzorzec), niektóre pomysły mają na celu znalezienie relacji powtarzania, stworzenie czegoś teleskopowego (lub potraktowanie tego jako funkcji generującej).
Skorzystamy z tych pomysłów tutaj.
Zauważ, że $ \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}$, albo to
$$ \frac{ 1 } { n-m } { n-m \choose m } = \frac{1}{n} \left[ { n - m \choose m } + { n - m - 1 \choose m- 1 } \right]. $$
To dobra zamiana, bo pozwala pozbyć się brzydkiego $ \frac{1}{n-k}$ co utrudnia nawrót, a także daje nam $\frac{1}{1991}$ po prawej stronie.
Zatem celem jest określenie $ \sum_{k=0}^{995 } (-1)^k \left[ {1991-k\choose k} + { 1991 - k - 1 \choose k - 1 } \right] $. (Pokażemy, że równa się 1, a zatem żądana suma to$\frac{1}{1991}.$)
Pozwolić $ S_n = \sum_{k=0}^{ \lfloor \frac{n}{2} \rfloor} (-1)^k { n-k \choose k } $.
Zauważ, że ${n-k \choose k } = { n-k - 1 \choose k } + { n-k - 1 \choose k - 1 } $, więc
$ 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}. $
(Uważaj na sprawdzanie indeksów i pamiętaj o nich ${n \choose m } = 0 $ kiedy $m > n $.)
Korzystając z tej relacji powtarzania i obliczając pewne wartości początkowe, otrzymujemy $S_n = 1 , 0, -1, -1, 0, 1, 1, 0, -1, \ldots$, który ma okres 6.
Chcemy zatem ustalić$S_{1991} - S_{1990} = 0 - (-1) = 1$.
Uwagi
Żałuję, że nie było tutaj argumentacji kombinatorycznej. Na przykład,$S_n$ ma natychmiastową interpretację jako różnicę między permutacjami parzystymi i nieparzystymi $p$ takie że $|p(i) - i | \leq 1$. (IE z pierwszego$n$ liczby całkowite są ${n-k \choose k }$sposoby na wybranie k par kolejnych liczb całkowitych (w sumie 2k). Perumatacja, która przełącza te pary i utrzymuje resztę na stałym poziomie, ma parzystość$k$.) Jednak nie widzę oczywistego sposobu, aby pokazać, że jest taka różnica $1, 0, -1, -1, 0, 1, \ldots $.
Wniosek WhatsUp, że o wartości $s_n$ wynika również z powyższego.
Jeśli znasz generowanie funkcji, oto rozwiązanie:
Pozwolić $s_n$ oznaczają sumę $\sum_{k \geq 0} \frac{(-1)^k}{n - k}\binom{n - k}k$ i pozwól $S(X)$ być formalnym szeregiem potęg $S(X) = \sum_{n \geq 1} s_n X^n$.
Obliczamy:
\ 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} gdzie$\omega = \frac{1 + \sqrt{-3}}2$ jest prymitywnym szóstym korzeniem jedności.
Tak mamy $s_n = \frac 1 n \cdot 2 \operatorname{Re}(\omega^n)$.
Teraz $\omega^n$ zależy tylko od $n \mod 6$. W związku z tym:$$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}$$
A odpowiedź na pierwotne pytanie wynika z tego $1991 \equiv 5 \mod 6$.