XLIV OM - I - Zadanie 6

Zawody matematyczne:

XLIV OM, 1992-1993

Etap:

Ciąg $(x_n)$ jest określony następująco:

$ x_0 = 1992, \quad x_n = -\frac{1992}{n} \cdot \sum_{k=0}^{n-1} x_k \quad \text{ dla } n\geq 1. $

Obliczyć sumę $\sum_{n=0}^{1992} 2^n x_n$ .

Rozwiązanie

Zastąpmy parametr $1992$ przez dowolnie ustaloną liczbę naturalną $N \geq 1$ i weźmy pod uwagę ciąg $(x_n)$ określony wzorami

$ x_0 = N, \quad x_n= -\frac{N}{n} \sum_{k=0}^{n-1} x_k \quad \textrm{dla } n = 1,2,3,\ldots; $

gdy $N = 1992$ , jest to ciąg dany w zadaniu.

Spróbujmy trochę poeksperymentować. Jeśli $N = 3$ , to początkowymi wyrazami ciągu $(x_n)$ są liczby $3$ , $-9$ , $9$ , $-3$ , Jeśli $N=4$ , to początkowymi wyrazami ciągu $(x_n)$ są liczby $4$ , $-16$ , $24$ , $-16$ , $4$ . Jeśli $N = 5$ , to początkowymi wyrazami ciągu $(x_n)$ są liczby $5$ , $-25$ , $50$ , $-50$ , $25$ , $-5$ . Te obserwacje prowadzą do przypuszczenia, że dla każdej liczby naturalnej $N \geq 1$ zachodzi równość

$ (1) \qquad x_n = (-1)^n N\binom{N}{n} \quad \textrm{dla } n = 0,1,2, \ldots,N. $

Udowodnimy, że tak jest istotnie. Przyda nam się w tym celu równość pomocnicza

$ (2) \qquad \sum_{k=0}^{n-1}(-1)^k \binom{N}{k} = (-1)^{n-1} \binom{N-1}{n-1}, $

zachodząca dla dowolnych liczb naturalnych $N \geq n \geq 1$ . Oto jej uzasadnienie:

Traktujemy $N$ jako ustalone. Dla $n = 1$ wzór (2) zachodzi. Załóżmy, że wzór (2) jest słuszny dla pewnego $n$ ( $1 \leq n \leq N- 1$ ). Skorzystamy z podstawowej własności współczynników dwumianowych:

$ \binom{N}{n} = \binom{N-1}{n-1} +\binom{N-1}{n}. $

Mnożymy obie strony tej równości przez $(-1)^n$ i dodajemy do odpowiednich stron równości (2):

$ \begin{split} \sum_{k=0}^{n-1}(-1)^k \binom{N}{k} &+(-1)^n \binom{N}{n} =\\ &=(-1)^{n-1} \binom{N-1}{n-1}+(-1)^n \binom{N-1}{n-1}+(-1)^n \binom{N-1}{n}; \end{split} $

krócej:

$ \sum_{k=0}^{n}(-1)^k \binom{N}{k} = (-1)^n \binom{N-1}{n}. $

Jest to równość (2) z $n$ zastąpionym przez $n+1$ . Na mocy zasady indukcji wzór (2) zachodzi dla $n = 1,2,\ldots ,N$ .

Przechodzimy do dowodu wzoru (1). Dla $n = 0$ wzór zachodzi. Weźmy dowolną liczbę naturalną $n$ (spełniającą warunki $1 \leq n \leq N$ ) i przyjmijmy indukcyjnie, że równość $x_k = (-1)^k N\binom{N}{k}$ (czyli (1) z $n$ zastąpionym przez $k$ ) zachodzi dla $k = 0,1,\ldots,n-1$ . Przekształcamy wyrażenie definiujące $x_n$ , korzystając ze wzoru (2):

$ \begin{split} x_n & = -\frac{N}{n} \sum_{k=0}^{n-1} (-1)^k N \binom{N}{k} = - \frac{N^2}{n}(-1)^{n-1} \binom{N-1}{n-1}=\\ &=(-1)^n N \cdot \frac{N}{n} \cdot\frac{(N-1)!}{(n-1)!(N-n)!}=(-1)^n N \binom{N}{n}. \end{split} $

Wykazaliśmy słuszność wzoru (1) dla wybranej liczby $n$ . Stąd, przez indukcję, wnosimy, że równość (1) zachodzi dla wszystkich $n \in \{1,2,\ldots,N\}$ .