How to resolve this problem with induction? $24|n^{6}-3n^{5}+6n^{4}-7n^{3}+5n^{2}-2n$ Is there some way to make induction step without use of Binomial formula and all that calculating?
Asked
Active
Viewed 85 times
0
-
If it needs to be induction, then probably, yes. But there are much easier ways to prove it. – Clayton Mar 09 '18 at 22:05
-
Thanks for the answer. Yes it must be induction, unfortunately. – Ana Mar 09 '18 at 22:07
-
Are you trying to prove it for all n, or just n > 0? – E.D. Mar 09 '18 at 22:07
-
Just $n>0$. $n$ is positive integer. – Ana Mar 09 '18 at 22:11
3 Answers
2
First, the base case $n=1$ is trivial but necessary.
This part is slightly tedious, but since you asked for induction, here.
Basically, we wish to prove that if we replace all occurrences of $n$ with $n+1$, we still have a multiple of 24.
From here, we can see that if $f(n) = n^6-3n^5+6n^4-7n^3+5n^2-2n$, then $f(n+1) = n^6 + 3 n^5 + 6 n^4 + 7 n^3 + 5 n^2 + 2 n$. From induction, it suffices to prove that the second expression is a multiple of 24 given that the first is.
Subtracting, we need to show that $$2n(3n^2+1)(n^2+2)$$ is a multiple of 24. If $n$ is odd, then $2n$ contains one factor of 2, $3n^2+1$ contains at least 2 factors of 2 (take modulo 4). If $n$ is even, then $2n$ contains two factors of 2, and $n^2+2$ contains one factor of $n$. We have shown that this is divisble by $8$ - we just need to show that this is divisible by 3 now.
If $n\equiv0\mod3$, then $2n$ is divisible by 3 and the proof is complete.
Or else, $n\equiv1, 2\mod3$, $n^2+2$ is divisible by 3 and we're done.
(Wolfram Alpha is not needed, but a time saver)
Nairit
- 517
-
-
-
Note that if $g(n)=n^{6}-3n^{5}+6n^{4}-7n^{3}+5n^{2}-2n$ then $g(n)=n(n-1)(n(n-1)+1)(n(n-1)+2)$. Using this factorization, it is easy to observe that $g(n+1)=g(-n) = n^{6}+3n^{5}+6n^{4}+7n^{3}+5n^{2}+2n$. – Math Lover Mar 09 '18 at 22:33
-
2
Every polynomial of degree $6$ satisfies the recursion $$f(n) = 7f(n-1) - 21f(n-2)+35f(n-3)-35f(n-4)+21f(n-5)-7f(n-6)+f(n-7)$$ So by induction if the first $7$ values are divisible by $24$ then all of them are.
Nate
- 11,206
-
-
1I'm not sure exactly what property you are referring to. In general, if a sequence satisfies a finite linear recursion like this with constant coefficients it is said to be $C$-finite. In this particular case for polynomials the recursion is coming from the "finite difference operator" $ D: f(x) \to f(x-1)$, the point being that $(D-1)^7$ kills any degree $6$ polynomial as applying $(D-1)$ lowers the degree. – Nate Mar 09 '18 at 22:32
-
"Every polynomial of degree 6 satisfies the recursion ..." This property. – Nairit Mar 09 '18 at 22:45
0
If you let $m=n(n-1)$ then your polynomial is $m(m+1)(m+2)$. This is a multiple of $3$, which you could show by induction. And $m$ is even, therefore $m+2$ is even and one of them must be a multiple of $4$, so the expression is a multiple of $8$. It's probably easier to show both of these facts by induction than to do the whole thing at once. For divisibility by $8$, you could drop the $m+1$ factor.
