LIV OM - I - Zadanie 4

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

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

$ 1^k + 2^k + 3^k + \ldots + m^k. $

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

$ \{i, i +1, i + 2, \ldots ,m\}. $

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

$ \begin{array}{l} 1\cdot(m^k-(m-1)^k)+2\cdot((m-1)^k-(m-2)^k)+3\cdot((m-2)^k-(m-3)^k)+\ldots\\ \qquad\qquad\qquad\qquad\qquad \ldots+(m-1)\cdot(2^k-1^k)+m\cdot 1^k=\\ \qquad=1^k+2^k+3^k+\ldots+m^k, \end{array} $

czego należało dowieść.