Solution:

Induction on $n$, then $m$. For $n = 1$, $2$ there is nothing to prove. Assume the result is proved for $< n$ and consider the case $n$.

If $n$ is odd, we have $n = n - 1 + 1 = n - 2 + 2 = \ldots = (n + 1)/2 + (n - 1)/2$, so the result is true for $m = n$, $k = (n + 1)/2$.

If $n$ is even, we have $n + 1 = n - 1 + 2 = \ldots = (n/2 + 1) + (n/2 - 1)$, so the result is true for $m = n + 1$ and $k = n/2$.

Now suppose it is true for $< m$.

If $2n > m > n + 1$, then for $m$ odd we can take the sums $m = n + m - n = n - 1 + m - n + 1 = \ldots = (m + 1)/2 + (m - 1)/2$. These use up the numbers $m - n$, $m - n + 1$, ..., $n$ and give some sums of $m$. By induction the remaining numbers $1, 2, \ldots, m - n - 1$ will give the remaining sums of $m$ (obviously $m > m - n - 1$).

If $m$ is even, we can take the sums $m = n + m - n = n - 1 + m - n + 1 = \ldots = (m/2 + 1) + (m/2 - 1)$. That gives some sums of $m$ and leaves us with the integers $1, 2, \ldots, m - n - 1$ and $m/2$. But since $m < 2(n + 1)$, $m/2 > m - n - 1$ and hence we can use the integers $1, 2, \ldots, m - n - 1$ to form sums of $m/2$. With the integer $m/2$ that gives us sums of $m$ (we know that the parity must come out right because we know that the sum of all the remaining numbers is divisible by $m$).

Finally, consider $m \geq 2n$. In that case we can form $k$ sums of $2n - 2k + 1$: $n + (n - 2k + 1)$, $(n - 1) + (n - 2k + 2)$, ..., $(n - k + 1) + (n - k)$. So we are home provided the remaining integers $1, 2, \ldots, n - 2k$ can be used to form $k$ sums of $m - (2n - 2k + 1)$. That follows by induction provided that $m - (2n - 2k + 1) \geq n - 2k$, or $m + 4k - 1 \geq 3n$, or $m + 2n(n + 1)/m - 1 \geq 3n$ or $(m - 2n)(m - n - 1) \geq 0$, which is true.