Математикадан облыстық олимпиада, 2015-2016 оқу жылы, 11 сынып

Кез келген натурал $n$ және $k$ сандары үшін, $\left( k+1 \right)!\cdot \left( {{1}^{k}}+{{2}^{k}}+\ldots +{{n}^{k}} \right)$ көбейтіндісінің $n\left( n+1 \right)$ санына бөлінетінін дәлелдеңіз.

Комментарий/решение

Решение. По Биному $(m+1)^{k+1}-m^{k+1}=∑_{j=0}^k {k+1 \choose j} m^j$. Просуммируем все такие тождества от $m=1$ до $m=n$: $(n+1)^{k+1}-1=∑_{j=0}^k {k+1\choose j} (1^j+2^j+⋯+n^j)$ (тождество Паскаля). Тогда $(k+1)!(1^k+2^k+⋯+n^k )=k![(n+1)^{k+1}-1-n-∑_{j=1}^{k-1}{k+1\choose j}(1^j+2^j+⋯+n^j)]$.

По предположению индукции (по $k$, база $k=1$ очевидна) каждое из $k!(1^j+2^j+⋯+n^j)$ делится на $n(n+1)$. Также $(n+1)^{k+1}-(n+1)$ делится на $n(n+1)$. Что и требовалось.

Ее можно решить с помощью LTE. Просто рассмотрите n = 2k, n = 2k + 1 и для каждого простого делителя из n и n + 1 использовать LTE