355*. Calculate the sum: $S_{k}=1^{k}+2^{k}+3^{k}+\ldots+n^{k}$.
Solution. Consider the difference:

$$
(p+1)^{k+1}-p^{k+1}=C_{k+1}^{1} p^{k}+C_{k+1}^{2} p^{k-1}+\ldots+1
$$

102

Setting $p=0,1,2 \ldots n$ successively, we get the equalities:

$$
\begin{aligned}
& 1^{k+1}=1 \\
& 2^{k+1}-1^{k+1}=C_{k+1}^{1} \cdot 1^{k}+C_{k+1}^{2} \cdot 1^{k-1}+\ldots+1 \\
& 3^{k+1}-2^{k+1}=C_{k+1}^{1} \cdot 2^{k}+C_{k+1}^{2} \cdot 2^{k-1}+\ldots+1 \\
& \cdot \cdot \cdot \dot{\cdot} \cdot \dot{*} \cdot \cdot \cdot \cdot \cdot \cdot \cdot \dot{\cdot} \cdot \cdot \cdot \cdot \cdot \\
&(n+1)^{k+1}-n^{k+1}=\dot{C_{k+1}^{1}} \cdot n^{k}+\dot{C_{k+1}^{2}} n^{k-1}+\ldots+\dot{1}
\end{aligned}
$$

Adding these equalities term by term, we get:

$$
(n+1)^{k+1}=C_{k+1}^{1} S_{k}+C_{k+1}^{2} S_{k-1}+\ldots+C_{k+1}^{1} S_{1}+n+1
$$

where $S_{i}$ is the sum of the $i$-th powers of the first $n$ natural numbers. Setting $k=1$, we get:

$$
(n+1)^{2}=2 S_{1}+n+1
$$

from which

$$
S_{1}=\frac{n(n+1)}{2}
$$

Setting $k=2$, we get:

$$
\begin{aligned}
& (n+1)^{3}=3 S_{2}+3 S_{1}+n+1= \\
& \quad=3 S_{2}+\frac{3 n(n+1)}{2}+n+1
\end{aligned}
$$

from which

$$
S_{2}=\frac{n(n+1)(2 n+1)}{6}
$$

Setting $k=3$, we get:

$$
(n+1)^{4}=4 S_{3}+6 S_{2}+4 S_{1}+n+1
$$

from which

$$
\begin{gathered}
S_{3}=\frac{1}{4}\left[(n+1)^{4}-(n+1)-6 S_{2}-4 S_{1}\right]= \\
=\frac{1}{4}\left[(n+1)^{4}-(n+1)-n(n+1) \cdot(2 n+1)-\right. \\
-2 n(n+1)]=\left[\frac{n(n+1)}{2}\right]^{2}
\end{gathered}
$$

thus

$$
1+2^{3}+\ldots+n^{3}=\left[\frac{n(n+1)}{2}\right]^{2}=S_{1}^{2}
$$

Therefore, the sum of any positive integer powers of the first $n$ natural numbers can be found.