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.
Please show me your proof.
Sorry if this question was already asked. Actually i did not found it. In that case only sharing the link will be enough.
On
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.
On
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.
On
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?
On
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}$$
On
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.
On
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)$$
@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.