1991 IMO Shortlist Problem $\#11$

Bei solchen Problemen (insbesondere wenn Sie feststellen, dass es ein allgemeines Muster gibt) besteht eine Idee darin, eine Wiederholungsbeziehung zu finden, etwas Teleskopisches zu erstellen (oder es als generierende Funktion zu behandeln).

Wir würden diese Ideen hier verwenden.

---

Beachte das $ \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}$, oder das

$$ \frac{ 1 } { n-m } { n-m \choose m } = \frac{1}{n} \left[ { n - m \choose m } + { n - m - 1 \choose m- 1 } \right]. $$

Dies ist eine gute Substitution, da es den nervigen loswird $ \frac{1}{n-k}$ Das macht die Wiederholung schwierig und gibt uns auch eine $\frac{1}{1991}$ auf der rechten Seite.

Ziel ist es also zu bestimmen $ \sum_{k=0}^{995 } (-1)^k \left[ {1991-k\choose k} + { 1991 - k - 1 \choose k - 1 } \right] $. (Wir werden zeigen, dass es gleich 1 ist und somit die gewünschte Summe ist$\frac{1}{1991}.$)

---

Lassen $ S_n = \sum_{k=0}^{ \lfloor \frac{n}{2} \rfloor} (-1)^k { n-k \choose k } $.

Beachte das ${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}. $

(Überprüfen Sie die Indizes sorgfältig und merken Sie sich diese ${n \choose m } = 0 $ wann $m > n $.)

Wenn wir diese Wiederholungsrelation verwenden und einige Anfangswerte berechnen, erhalten wir $S_n = 1 , 0, -1, -1, 0, 1, 1, 0, -1, \ldots$, die Periode 6 hat.
Wir wollen also bestimmen$S_{1991} - S_{1990} = 0 - (-1) = 1$.

---

Anmerkungen

1. Ich wünschte, es gäbe hier ein kombinatorisches Argument. Beispielsweise,$S_n$ hat eine unmittelbare Interpretation als Unterschied zwischen geraden und ungeraden Permutationen $p$ so dass $|p(i) - i | \leq 1$. (IE aus dem ersten$n$ ganze Zahlen gibt es ${n-k \choose k }$Möglichkeiten, k Paare aufeinanderfolgender Ganzzahlen auszuwählen (für insgesamt 2k). Die Perumatation, die diese Paare wechselt und den Rest festhält, hat Parität$k$.) Ich sehe jedoch keinen offensichtlichen Weg, um zu zeigen, dass dieser Unterschied besteht $1, 0, -1, -1, 0, 1, \ldots $.

2. WhatsUps Schlussfolgerung, dass über den Wert von $s_n$ folgt auch aus dem oben Gesagten.

Wenn Sie wissen, wie man Funktionen generiert, finden Sie hier eine Lösung:

Lassen $s_n$ bezeichnen die Summe $\sum_{k \geq 0} \frac{(-1)^k}{n - k}\binom{n - k}k$ und lass $S(X)$ sei die formale Potenzreihe $S(X) = \sum_{n \geq 1} s_n X^n$.

Wir berechnen:

\ 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} where$\omega = \frac{1 + \sqrt{-3}}2$ ist eine primitive sechste Wurzel der Einheit.

So haben wir $s_n = \frac 1 n \cdot 2 \operatorname{Re}(\omega^n)$.

Jetzt $\omega^n$ hängt nur ab von $n \mod 6$. Deshalb:$$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}$$

Und die Antwort auf die ursprüngliche Frage ergibt sich aus der Tatsache, dass $1991 \equiv 5 \mod 6$.