Hi All!
I was wondering if anyone was able to potentially help me out with a Mathematical Induction Question below. Thank you!
Prove by induction that n^5− n is divisible by 240 for each odd positive integer n.
Yeah, so the trick with these types of induction proofs is you want to show that the LHS turns into some RHS that's equal to 240*(some number). For example, 480 is a multiple of 240 because 480=240*(2). If you were to get something disgusting out the end that looks like n^5-n=240*(n^100 - n^432 + 54432323n^2 + 5 - 45n) or something else that stupid, it's still 240*(some number), and so is still divisible by 240. Since it's an odd number, you also need to make sure your inductive proof only goes through odd numbers. There are two ways to do this:
1. Prove this is true for n=2m+1, instead of for n, or:
2. Make sure your base case is an odd number (so, start with n=1), then prove it true for n=k+2 instead of n=k+1 (WHY would this work??)
Otherwise, it's still an inductive proof at its heart. I want you to try this out for yourself first, so here's an example using an example question that you can use to see my hints in action:
Prove by induction that n3-n is divisible by 24 for all odd positive integersSo, first, the base case - n=1:
Which is divisible by 24. So, step 2 - assume it's true for n=k.
... Done
Okay, step 3. Let's see if this is true for n=k+2:
Okay, so we know that k^3-k is divisible by 24, so I'm going to substitute a 24x into there - because we don't care WHAT value it is exactly, just that it IS divisible by 24. I also know that k is an odd number, so k+1 HAS to be even - so I'm just going to call that 2y. Because again, I don't care EXACTLY what the number is, I just care about what it's divisible by. So this gives me:
Which is a multiple of 24, and completes the proof
---
So, some questions I often get asked:
a) how did I know to make that expansion and factorisation in the steps?
I didn't - but it was either do that or do anything. With all of these proofs, I have no idea what direction I need to move. But, if I don't move forwards, I won't get anywhere - expanding at the start is the only thing I could do, so I did it. And every time I expand something, I expect I need to factorise it later, so when I recognise something I CAN factorise - I do it. If I factorise, and it turns out that that's NOT useful, then I can always just expand it in the next step and move on.
b) how did I know to make k+1=2y?
I didn't. All I know is, the more I can reduce things to stuff they're divisible by, the easier these proofs become - so I saw I could turn k+1 into a multiple of something, and I ran from there.
---
Also, if you're interested, here's how you'd do it using the set n=2m+1 method.
Step 1: Prove this is true for the base case, m=0:
Done, simple. Now, assume this is true for m=k
... Done
Now, let's test m=k+1:
From here, just pick another variable (say, L=2k+1), and this follows the same steps as the one above.