XLIV OM - I - Zadanie 6

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

\[<br />
x_0 = 1992, \quad x_n = -\frac{1992}{n} \cdot \sum_{k=0}^{n-1} x_k \quad \text{ dla } n\geq 1.<br />
\]

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

\[<br />
x_0 = N,    \quad  x_n= -\frac{N}{n} \sum_{k=0}^{n-1} x_k   \quad   \textrm{dla }  n = 1,2,3,\ldots;<br />
\]

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ść

\[<br />
(1) \qquad  x_n = (-1)^n N\binom{N}{n} \quad   \textrm{dla }   n = 0,1,2, \ldots,N.<br />
\]

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

\[<br />
(2) \qquad  \sum_{k=0}^{n-1}(-1)^k \binom{N}{k} = (-1)^{n-1} \binom{N-1}{n-1},<br />
\]

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:

\[<br />
\binom{N}{n} = \binom{N-1}{n-1} +\binom{N-1}{n}.<br />
\]

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

\[<br />
\begin{split}<br />
\sum_{k=0}^{n-1}(-1)^k \binom{N}{k} &+(-1)^n \binom{N}{n} =\\<br />
&=(-1)^{n-1} \binom{N-1}{n-1}+(-1)^n \binom{N-1}{n-1}+(-1)^n \binom{N-1}{n};<br />
\end{split}<br />
\]

krócej:

\[<br />
\sum_{k=0}^{n}(-1)^k \binom{N}{k} = (-1)^n \binom{N-1}{n}.<br />
\]

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):

\[<br />
\begin{split}<br />
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}=\\<br />
&=(-1)^n N \cdot \frac{N}{n} \cdot\frac{(N-1)!}{(n-1)!(N-n)!}=(-1)^n N \binom{N}{n}.<br />
\end{split}<br />
\]

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

A wobec tego

\[<br />
\sum_{n=0}^N 2^n x_n =\sum_{n=0}^N 2^n (-1)^n N \binom{N}{n}= N\sum_{n=0}^N  \binom{N}{n} (-2)^n 1^{N-n}.<br />
\]

Figurująca w ostatnim wyrażeniu suma jest rozwinięciem (Newtona) $ N $-tej potęgi dwumianu $ (-2 + 1) $. Zatem

\[<br />
\sum_{n=0}^N 2^n x_n= N\cdot (-2+1)^N =(-1)^N \cdot N.<br />
\]

Jest to szukana wartość. Dla $ N = 1992 $ wynosi ona $ 1992 $.

Komentarze

Dodaj nową odpowiedź