Mathematic induction - prove n^5 - n is divisible by 240 when n is a positive odd integer

ausmathgenius420

ausmathgenius420

New member
Joined
Aug 5, 2021
Messages
44
Hi:)

I'm really struggling with the question in the title.

[math]n^5-n[/math]
I have just learnt how to do regular division proofs, but n being odd is really tricking me.
I'm assuming after proving the basis step p(1) you would do:
[math]n^5-n=240x[/math]
I've tried factorising n=k+1 and n=k+2 and I can't rearrange either of them to be divisible by 240 so I'm quite lost.

Thanks,
 
After step 1 you need to assume that \(\displaystyle k^5-k\) is divisible by \(\displaystyle 240\) for pos odd integer \(\displaystyle k\) and prove that \(\displaystyle (k+2)^5-(k+2)\) is divisible by 240.
Have you expanded \(\displaystyle (k+2)^5-(k+2)\)? What do you get at this stage?
 
Harry_the_cat said:
After step 1 you need to assume that \(\displaystyle k^5-k\) is divisible by \(\displaystyle 240\) for pos odd integer \(\displaystyle k\) and prove that \(\displaystyle (k+2)^5-(k+2)\) is divisible by 240.
Have you expanded \(\displaystyle (k+2)^5-(k+2)\)? What do you get at this stage?
Click to expand...
I get a large polynomial however I can't seem to factor out 240 from it. From that large polynomial I have also tried subbing in 240(m) for [imath]k^5-k[/imath] but I still cannot factor 240 out.

The polynomial is [math]k^5+10k^4+40k^3+80k^2+79k+30[/math]
Which could be rearranged so that [math]240m+10k^4+40k^3+80k^2+80k+30[/math] however this doesn't solve my factoring problem. Hopefully I'm just missing something little?
 
What you have then is a polynomial whose first term is divisible by 240. You now need to prove that the rest of it is also div by 240.
The rest is \(\displaystyle 10(k^4+4k^3+8k^2+8k+3)\). I factorised out the 10 to keep the numbers smaller. So you need to show that the bracketed expression is div by 24.
You now need to start another Proof by induction on just this bit. So back to Step 1, ie check that k=1 works and then step 2 (working of course with \(\displaystyle k+2\) in place of \(\displaystyle k\).
You may need to do this again and maybe again. Very satisfying when it all comes out nicely. Watch your coefficients - get one wrong and it stuffs everything up ! Enjoy!
Let me know how it goes!
 
[math]k^4+12k^3+56k^2+120k+99[/math]
--> cancel the 120k

[math]k^4+20k^3+152k^2+400k+435[/math]
Nothing is divisible by 24 here?

Should I be using (2k+1) to represent the odd number instead?
 
No k+2 is correct. because you tested an odd number in step 1.

Don't forget to use your assumption. That will knock out the \(\displaystyle k^4 \) term
 
Ok when you expand you get
1643635628212.png
which is correct.
Don't forget that in the Induction proof you are assuming that
1643635698078.png is divisible by 24.

Now 1643635744275.png= 1643635757660.png +\(\displaystyle 8k^3+48k^2+112k+96\)

\(\displaystyle =24 n + 8k^3+48k^2+112k+96\)

Remember you are trying to prove that this expression is div by 24,
The first term is, so now you have to prove that \(\displaystyle 8k^3+48k^2+112k+96 = 8(k^3+6k^2+14k+12)\) is div by 24
ie that the bracket is div by 3.

So another induction proof. This time prove that \(\displaystyle k^3+6k^2+14k+12\) is divisible by 3. Start over again.

So this whole process involves an induction proof within an induction proof within an induction proof ... until you exhaust the process.

Does that make sense?
 
@Cubist (after reading your reply to my rant)
You can shortcut the next step.
\(\displaystyle k^3+6k^2+14k+12 = 3(2k^2 +4) + k^3+14k\)
Because the first term is div by 3, you really only need to prove that \(\displaystyle k^3+14k\) is div by 3 (for odd k).
 
I would go about this in a somewhat different way. I'd start by focusing on the fact that we are dealing with ODD numbers. We are not talking about [imath]n^5 - n[/imath] at all, but rather about

[math]y_n = (2n - 1)^5 - (2n - 1) =\\ 32(1)n^5 - 16(5)n^4 + 8(10)n^3 - 4(10)n^2 + 2(5)n - 1 - (2n -1) =\\ 32n^5 - 80n^4 + 80n^3 - 40n^2 + 10n - 1 - 2n + 1 = \\ 32n^5 - 80n^4 + 80n^3 - 40n^2 + 8n.[/math]
It is then instantly obvious that [imath]y_n[/imath] is divisible by eight. That leads to the thought that the prime factorization of 240 may be relevant. We note [imath]240 = 2^4 * 3 * 5 = 16 * 3 * 5.[/imath]

The proposition to be proved is

[math]\text {For any positive integer } n, \ 240 \ | \ y_n.[/math]
Proving the base case for induction is almost obvious by inspection.

[math]\text {By definition, } y_1 = (2 * 1 - 1)^5 - (2 * 1 - 1) = 1^5 - 1 = 0 = 240 * 0.\\ \therefore 240 \ | \ y_1.[/math]
We set up the induction step:

[math]k \text { is an integer } \ge 1 \text { such that } 240 \ | \ y_k.\\ \therefore 3 \ | \ y_k, \ 5 \ | \ y_k, \text { and } 16 \ | \ y_k.\\ \text {Thus, } \exists \text { an integer } m_k \text { such that } 240m_k = y_k.\\ \text {And, by definition, } y_k = 32k^5 - 80k^4 + 80k^3 - 40k^2 + 8k.\\ \therefore 240 m_k = 32k^5 - 80k^4 + 80k^3 - 40k^2 + 8k.[/math]
[math]y_{k+1} = \{2(k +1) - 1\}^5 - \{2(k + 1) - 1) = (2k + 1)^5 - (2k + 1) =\\ 32k^5 + 80k^4 + 80k^3 + 40k^2 + 10k + 1 - 2k - 1 =\\ 32k^5 + 80k^4 + 80k^3 + 40k^2 + 8k.[/math]
[math]y_{k+1} - y_k = 160k^4 + 80k^2.\\ \text {But } y_k = 240m_k \implies y_{k + 1} - 240m_k = 160k^4 + 80k^2 \implies\\ y_{k+1} = 240m_k + 160k^4 + 80k^2.\\ \therefore y_{k+1} = 80(3m_k + 2k^4 + k^2) \text { and }\\ 3m_k + 2k^4 + k^2 \text { is an integer} \implies 80 \ | \ y_{k+1} \implies\\ 5 \ | \ y_{k+1} \text { and } 16 \ | \ y_{k+1}.[/math]
Now this is not an approach that will obviously give us [imath]3 \ | \ y_{k+1}[/imath]. But

[math]\exists \text { a pair of integers } p \text { and } q \text { such that } 3p + q = k \text { and } 0 \le q \le 2 \implies\\ y_{k+1} = 32(3p + q)^5 + 80(3p + q)^4 +\\ 80(3p + q)^3 + 40(3p + q)^2 + 8(3p + q) =\\ 3p * \text { stuff} + q(32 + 80 + 80 + 40 + 8) =\\ 3p * \text { stuff} + 240q = 3(p + 80q) \implies 3 \ | \ y_{k+1}.[/math]
Once we know that 3, 5, and 16 all divide [imath]y_{k+1}[/imath], it's all over bar the shouting.
 
This is marginally relevant to this thread, but: the statement seems simpler to prove without induction. Indeed,[math]y = n^5-n = (n-1)n(n+1)(n^2+1)[/math] so:
  • y is divisible by 5 because of the Fermat's Little Theorem;
  • y is divisible by 3 because $(n-1)n(n+1)$ is a product of three consecutive integers;
  • y is divisible by 16 because [imath]n[/imath] is odd so there are 3 even numbers in the product and between [imath]n-1[/imath] and [imath]n+1[/imath] one of them must be divisible by 4.
 
blamocur said:
This is marginally relevant to this thread, but: the statement seems simpler to prove without induction. Indeed,[math]y = n^5-n = (n-1)n(n+1)(n^2+1)[/math] so:
  • y is divisible by 5 because of the Fermat's Little Theorem;
  • y is divisible by 3 because $(n-1)n(n+1)$ is a product of three consecutive integers;
  • y is divisible by 16 because [imath]n[/imath] is odd so there are 3 even numbers in the product and between [imath]n-1[/imath] and [imath]n+1[/imath] one of them must be divisible by 4.
Click to expand...
I agree. But it seems that a proof by induction was requested. Also, I was interested in utlilizing the constraint that this concerned odd numbers.
 
Following the advice of @Harry_the_cat posts above, I did the following work (I've never done an inductive proof within an inductive proof before and found this very interesting, thanks 'Arry :))

Prove f(n) = n^5 - n is divisible by 240 for odd n

Base case f(1) = 0 which is divisible by 240

Assume true for n=k...

\(\displaystyle k^5 - k\) is divisible by 240 (1)

is it true for n=k+2?

\(\displaystyle (k+2)^5 - (k + 2)\)

\(\displaystyle = \color{red}(k^5 - k)\color{black} + 10k^4 + 40k^3 + 80k^2 + 80k + 30\)

true if \(\displaystyle 10k^4 + 40k^3 + 80k^2 + 80k + 30\) is divisible by 240, by using (1) to eliminate the red

\(\displaystyle = 10( k^4 + 4k^3 + 8k^2 + 8k + 3 )\) see next proof by induction


Prove \(\displaystyle g(n) = n^4 + 4n^3 + 8n^2 + 8n + 3\) is divisible by 24 for odd n

Base case g(1) = 24 which is divisible by 24

Assume true for n=k

\(\displaystyle k^4 + 4k^3 + 8k^2 + 8k + 3\) is divisible by 24 (2)

is it true for n=k+2?

\(\displaystyle (k+2)^4 + 4(k+2)^3 + 8(k+2)^2 + 8(k+2) + 3\)

\(\displaystyle = k^4 + 12k^3 + 56k^2 + 120k + 99\)

\(\displaystyle = \color{red}(k^4 + 4k^3 + 8k^2 + 8k + 3)\color{black} + 8k^3 + 48k^2 + 112k + 96\)

true if \(\displaystyle 8k^3 + 48k^2 + 112k + 96\) is divisible by 24, by using (2) to eliminate the red

\(\displaystyle = 8( k^3 + 6k^2 + 14k + 12 )\) see next proof by induction

Prove \(\displaystyle n^3 + 6n^2 + 14n + 12\) is divisible by 3

\(\displaystyle = n^3 + 14n + 3(2n^2 + 4)\)

Only need to prove that \(\displaystyle h(n) = n^3 + 14n\) is divisible by 3 for odd n

Base case h(1) = 15 which is divisible by 3

Assume true for n=k

\(\displaystyle k^3 + 14k \) is divisible by 3 (3)

is it true for n=k+2?

\(\displaystyle (k+2)^3 + 14*(k+2)\)

\(\displaystyle = k^3 + 6k^2 + 26k + 36\)

\(\displaystyle = \color{red}(k^3 + 14k)\color{black} + 6k^2 + 12k + 36\)

true if \(\displaystyle 6k^2 + 12k + 36\) is divisible by 3, using (3) to eliminate the red

\(\displaystyle = 6k^2 + 12k + 36\)

\(\displaystyle = 6( k^2 + 2k + 6 )\) divisible by 3

All the base cases and inductive steps above have been proved correct. Therefore by mathematical induction the original statement \(\displaystyle f(n) = n^5 - n\) is divisible by 240 is true for every positive odd natural number n.
 
Since n5-n = 0 for n=1, shouldn't there be restriction of n>1 and in that case the base case should be n = 3.
 
Subhotosh Khan said:
Since n5-n = 0 for n=1, shouldn't there be restriction of n>1 and in that case the base case should be n = 3.
Click to expand...
That's a very good question. I certainly found it very unsatisfying to state that 0 is divisible by 240. But I do think that it's OK, and I'd be very interested to see what other people think.

The divisibility works for all odd negative n also, but I guess this proof by induction doesn't prove it. I guess that in order to prove this, by induction, we'd have to repeat the proof for n=k-2 ?
 
You must log in or register to reply here.
Top