Prove that $\frac{k^7}{7}+\frac{k^5}{5}+\frac{2k^3}{3}-\frac{k}{105}$ is an integer.

We have: $$\frac{k^7}{7}+\frac{k^5}{5}+\frac{2k^3}{3}-\frac{k}{105} =\frac{15k^7+21k^5+70k^3-k}{3\cdot 5\cdot 7} $$ To prove this is an integer we need that: $$15k^7+21k^5+70k^3-k\equiv 0 \pmod{3\cdot 5\cdot 7}$$ According to the Chinese Remainder Theorem, this is the case iff $$\begin{cases}15k^7+21k^5+70k^3-k\equiv 0 \pmod{3} \\ 15k^7+21k^5+70k^3-k\equiv 0 \pmod{5}\\ 15k^7+21k^5+70k^3-k\equiv 0 \pmod{7}\end{cases} \iff \begin{cases}k^3-k\equiv 0 \pmod{3} \\ k^5-k\equiv 0 \pmod{5}\\ k^7-k\equiv 0 \pmod{7}\end{cases}$$ Fermat's Little Theorem says that $k^p\equiv k \pmod{p}$ for any prime $p$ and integer $k$.

Therefore the original expression is an integer.


@I like Serena has a great answer but since the OP asked for a proof by induction, I'll show what that would look like. Define $$f(k)=\frac{k^7}{7}+\frac{k^5}{5}+\frac{2k^3}{3}-\frac{k}{105}=\frac{15k^7 + 21k^5+70k^3-k}{105}$$

For our base case, let $k=1$. Then we have $$f(1)=\frac{15+21+70-1}{105}=1$$ which is an integer. Now suppose $f(k)$ is an integer for some $k\geq 1$. We want to prove that $f(k+1)$ is also an integer. To that end, observe that \begin{align} f(k+1)&=\frac{15(k+1)^7 + 21(k+1)^5+70(k+1)^3-(k+1)}{105}\\ &=\frac{15k^7 + 105k^6+336k^5+630k^4 + 805k^3+735k^2+419k+105}{105} \end{align} Therefore \begin{align} f(k+1)-f(k)&=\frac{105k^6+315k^5+630k^4+735k^3+735k^2+420k+105}{105}\\ &=\frac{105(k^6+3k^5+6k^4+7k^3+7k^2+4k+1)}{105}\\ &= k^6+3k^5+6k^4+7k^3+7k^2+4k+1 \end{align} Which is an integer, say $N$. Rearranging this gives $f(k+1)=f(k)+N$ and since $f(k)$ is assumed to be an integer from the induction hypothesis, $f(k+1)$ is the sum of two integers, hence an integer.


Call the expression $f(k)$. As it's a degree $7$ polynomial, it obeys the recurrence $$\sum_{j=0}^8(-1)^j\binom8jf(k-j)=0.$$ Thus $$f(k)=8f(k-1)-28f(k-2)+56f(k-3)-70f(k-4)+56f(k-5)-28f(k-6)+8f(k-7)-f(k-8)$$ so that if $f$ takes eight consecutive integer values, by induction, all subsequent values are integers too.