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

## marked as duplicate by Bill Dubuque algebra-precalculus StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 16 at 20:41

• Put all terms on common denominator and prime factor the denominator and if possible numerator. – mathreadler Jan 16 at 17:00
• It is $15k^7+21k^5+70k^3-k$ – M Desmond Jan 16 at 17:01
• You now need everything to be divisible by $105 = 3\cdot 5\cdot 7$ – mathreadler Jan 16 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 – M Desmond Jan 16 at 17:10
• Read this marvelous answer on how to make an induction proof work – Ross Millikan Jan 16 at 17:11

@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 – M Desmond Jan 16 at 17:41

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! – mathreadler Jan 16 at 17:12
• Excellent answer! – manooooh Jan 16 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? – EuxhenH Jan 16 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. – Klaas van Aarsen Jan 16 at 17:22
• @EuxhenH an integer raised to an integer is always an integer because integers are closed under multiplication and addition. – mathreadler Jan 16 at 17:22

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? – mathreadler Jan 16 at 17:20
• @mathreadler iterated differences. – Lord Shark the Unknown Jan 16 at 17:21
• Does it work only with 7 degree ? Please give a reference where i can find this relations ! – M Desmond Jan 16 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. – Bill Dubuque Jan 16 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\$ – Bill Dubuque Jan 16 at 19:18
• They are similar but my equality we can see immediately. See please better that I wrote. – Michael Rozenberg Jan 16 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). – Bill Dubuque Jan 16 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. – Michael Rozenberg Jan 16 at 19:31
• How do you propose that one "sees" things like that in general? – Bill Dubuque Jan 16 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. – Bill Dubuque Jan 16 at 19:35