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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź