L OM - II - Zadanie 6

Zawody matematyczne:

L OM, 1998-1999

Etap:

Dana jest liczba naturalna $k \geq 2$ oraz liczby całkowite $a_1, a_2,\ldots, a_n$ spełniające warunki

$ a_1 + 2^i a_2 + 3^i a_3 + \ldots + n^i a_n = 0\ \textrm{dla}\ i = 1, 2,\ldots, k-1. $

Dowieść, że liczba $a_1 + 2^k a_2 + 3^k a_3 + \ldots + n^k a_n$ jest podzielna przez $k!$ .

Rozwiązanie

Dla dowolnej liczby całkowitej $m \geq k$ liczba ${m \choose k}$ jest całkowita. Stąd dla dowolnej liczby całkowitej dodatniej $m$ liczba $m(m-1)(m-2)\ldots(m-k+1)$ jest podzielna przez $k!$ . Istnieją więc takie liczby całkowite $b_1,b_2,\ldots,b_{k-1}$ , że dla dowolnej liczby całkowitej dodatniej $m$ ,

$ m^k \equiv b_1m+b_2m^2 +\ldots+b_{k-1}m^{k-1} (\mathrm{mod}\ k!). $

Mnożąc powyższą kongruencję przez $a_m$ , a następnie dodając stronami od $m =1$ do $m = n$ otrzymujemy

$ \begin{split} a_1 +2^ka_2 +\ldots+n^ka_n \equiv & b_1(a_1 +2a_2 +\ldots+na_n)+b_2(a_1 +2^2a_2 +\ldots+n^2 a_n)+\ldots \\ &\qquad\ldots+b_{k-1}(a_1 +2^{k-1}a_2 +\ldots+n^{k-1}a_n)= \\ &= 0 (\mathrm{mod}\ k!). \end{split} $