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

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

I tried using mathematical induction but using binomial formula also it becomes little bit complicated.

• Put all terms on common denominator and prime factor the denominator and if possible numerator. Jan 16, 2019 at 17:00
• It is $15k^7+21k^5+70k^3-k$ Jan 16, 2019 at 17:01
• You now need everything to be divisible by $105 = 3\cdot 5\cdot 7$ Jan 16, 2019 at 17:05
• Sorry ! I did not get what you want to point out. If you are saying about proving divisibility it is still a task : how to prove it by induction ? The p:k+1 will contain nearly 20 terms Jan 16, 2019 at 17:10
• Read this marvelous answer on how to make an induction proof work Jan 16, 2019 at 17:11

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.

• Nice. You are a fast writer! Jan 16, 2019 at 17:12
• Excellent answer! Jan 16, 2019 at 17:15
• Fermat's Little Theorem says that if $p$ is prime and $k$ is an integer, then we have $k^p=k$ (mod $p$). How does it follow from $k^p=k$ (mod $p$) that $k$ is an integer? Jan 16, 2019 at 17:19
• It doesn't @EuxhenH. I just stated the result first and the conditions afterwards. It's exactly how you say it is. Jan 16, 2019 at 17:22
• @EuxhenH an integer raised to an integer is always an integer because integers are closed under multiplication and addition. Jan 16, 2019 at 17:22

@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.

• Thanks 4 your effort Jan 16, 2019 at 17:41

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.

• Very interesting. What causes the recurrence equation? Jan 16, 2019 at 17:20
• @mathreadler iterated differences. Jan 16, 2019 at 17:21
• Does it work only with 7 degree ? Please give a reference where i can find this relations ! Jan 16, 2019 at 17:31
• @MDesmond $\Delta f(k) := f(k+1)-f(k)\,$ reduces the degree of the polynomial $\,f(k)\,$ since leading terms cancel. So if $f$ has degree $n$ then $\,\Delta^{n+1} f(k) = 0\,$ yields a recurrence for $f(k).\,$ Above is the binomial expansion using $\,\Delta = S-1\,$ where $\,S\,f(k) = f(k+1)\,$ is the shift operator. See any textbook that treats recurrences or finite differences. Jan 16, 2019 at 20:01

hint...if you only want to use induction, let $$f(k)=15k^7+21k^5+70k^3-k$$ and consider $$f(k+1)-f(k)=$$

For the induction step you have to show this is divisible by $$105$$

So, for example, $$(k+1)^7-k^7=7N+1$$ where $$N$$ is an integer, etc...

Can you finish?

You can use the binomial transform to prove that

$$\frac{k^7}{7}+\frac{k^5}{5}+\frac{2k^3}{3}-\frac{k}{105} \\={k\choose1}+28{k\choose2}+292{k\choose3}+1248{k\choose4}+2424{k\choose5}+2160{k\choose6}+720{k\choose7}$$

Base case for $$k=1$$: $$\frac{1^7}{7}+\frac{1^5}{5}+\frac{2*1^3}{3}-\frac{1}{105}=1$$

Now, assume for some k that $$\frac{k^7}{7}+\frac{k^5}{5}+\frac{2k^3}{3}-\frac{k}{105}$$ is indeed in integer.

Then $$\frac{(k+1)^7}{7}+\frac{(k+1)^5}{5}+\frac{2(k+1)^3}{3}-\frac{k+1}{105}=\\\frac{\sum_{i=0}^7\binom{7}{i}k^i}{7}+\frac{\sum_{i=0}^5\binom{5}{i}k^i}{5}+2\frac{\sum_{i=0}^3\binom{3}{i}k^i}{3}-\frac{k+1}{105}=$$

Extracting the highest indexed term from each sum (and the $$-\frac{k}{105}$$ at the end): $$\frac{k^7}{7}+\frac{k^5}{5}+\frac{2k^3}{3}-\frac{k}{105}+\frac{\sum_{i=0}^6\binom{7}{i}k^i}{7}+\frac{\sum_{i=0}^4\binom{5}{i}k^i}{5}+2\frac{\sum_{i=0}^2\binom{3}{i}k^i}{3}-\frac{1}{105}$$

By the induction hypothesis, the sum of the first four terms is an integer so, if we can show the rest of the above sum is an integer, we will be done. Use the fact that, for any prime, $$p$$, $$p|\binom{p}{k}$$ where $$1\leq k\leq p-1$$. This is because $$\binom{p}{k}=\frac{p(p-1)...(p-k+1)}{k(k-1)...1}$$

$$p$$ divides the numerator but not the denominator (as $$1\leq k\leq p-1$$) so $$p|\binom{p}{k}$$

So each term in the remaining sum with index $$i$$ $$\geq1$$ and $$\leq p-1$$ ($$p$$ being the respective prime in each sum) is divisible by the corresponding $$p$$ in the denominator and produces an integer. The only non-integer terms left will be the ones at $$i=0$$, i.e. $$\frac{\binom{7}{0}k^0}{7}+\frac{\binom{5}{0}k^0}{5}+\frac{2\binom{3}{0}k^0}{3}-\frac{1}{105}=\frac{1}{7}+\frac{1}{5}+\frac{2}{3}-\frac{1}{105}=1$$

So $$\frac{(k+1)^7}{7}+\frac{(k+1)^5}{5}+\frac{2(k+1)^3}{3}-\frac{k+1}{105}$$ is a sum of integers making it an integer.

Because $$\frac{k^7}{7}+\frac{k^5}{5}+\frac{2k^3}{3}-\frac{k}{105}=\frac{k^7-k}{7}+\frac{k^5-k}{5}+\frac{2(k^3-k)}{3}+k.$$

• Same as my answer after dividing by $\,3\cdot 5\cdot 7\$ Jan 16, 2019 at 19:18
• They are similar but my equality we can see immediately. See please better that I wrote. Jan 16, 2019 at 19:20
• In my experience most students don't "immediately" see such fraction expansions.. Rather they first put it over a common denominator, as I did. From that it is easy to read off the fraction expansion (but there is no need to rewrite the key (Fernat) divisibilities in fraction form). Jan 16, 2019 at 19:28
• I think you see that $-\frac{1}{105}=-\frac{1}{7}-\frac{1}{5}-\frac{2}{3}+1$. If so, we are done! I think, it's much more better than your writing. Jan 16, 2019 at 19:31
• How do you propose that one "sees" things like that in general? Jan 16, 2019 at 19:32

Hint  Note that $$\ 3\!\cdot\!5\!\cdot\!7\mid \overbrace{3\!\cdot\! 5\, (\color{#c00}{k^7\!-\!k})+ 3\!\cdot\! 7\, (\color{#c00}{k^5\!-\!k})- 5\!\cdot\! 7 (\color{#c00}{k^3\!-\!k})+ 3\!\cdot\! 5\cdot\! 7\, k^3}^{\Large{\rm sum\ = \ this/(3\cdot 5\cdot 7)}}\,$$ by $$\,\rm\overbrace{little\ \color{#c00}{Fermat}}^{\Large p\ \mid\ \color{#c00}{k^p-k}}$$

Remark  More generally this shows that if $$\,p,q,r\,$$ are primes and $$\,a,b,c,k\,$$ are integers

$$\quad\ pqr\,\mid\, aqr\,(k^p\!-\!k)+bpr\,(k^q\!-\!k)+cpq\,(k^r\!-\!k)$$

• Note that we don't actually have to recognize the above form to prove it is $\equiv 0\pmod{p}\,$ for $\,p = 3,5,7,\,$ since simply computing it $\!\bmod p\,$ using $\,k^p\equiv k\,$ easily proves it is $\equiv 0,\$ But I showed the form of the expression to reveal how it was constructed. Jan 16, 2019 at 19:35