LIV OM - I - Zadanie 4

Rozpatrujemy zbiór wszystkich $ k $-wyrazowych ciągów o wyrazach ze zbioru $ \{1, 2, 3,\ldots , m\} $. Z każdego takiego ciągu wybieramy wyraz najmniejszy i sumujemy wybrane wyrazy. Udowodnić, że otrzymana suma jest równa

\[<br />
1^k + 2^k + 3^k + \ldots + m^k.<br />
\]

Rozwiązanie

Oznaczmy przez $ L_i $ $ (i =1,2,\ldots,m) $ liczbę tych $ k $-wyrazowych ciągów o wyrazach ze zbioru $ \{1, 2, 3, \ldots , m\} $, których każdy wyraz jest nie mniejszy niż $ i $. Ciągi takie to $ k $-wyrazowe ciągi o wyrazach z $ (m-i+1) $-elementowego zbioru

\[<br />
\{i, i +1, i + 2, \ldots ,m\}.<br />
\]

Stąd wynika, że $ L_i = (m-i+1)^k $. Zatem liczba ciągów o najmniejszym wyrazie równym $ i $ wynosi $ L_i - L_{i+1} = (m - i + 1)^k - (m - i)^k $.

Suma wszystkich wyrazów najmniejszych jest więc równa

\[<br />
\begin{array}{l}<br />
1\cdot(m^k-(m-1)^k)+2\cdot((m-1)^k-(m-2)^k)+3\cdot((m-2)^k-(m-3)^k)+\ldots\\<br />
\qquad\qquad\qquad\qquad\qquad \ldots+(m-1)\cdot(2^k-1^k)+m\cdot 1^k=\\<br />
\qquad=1^k+2^k+3^k+\ldots+m^k,<br />
\end{array}<br />
\]

czego należało dowieść.

Komentarze

Dodaj nową odpowiedź