# Induction, proving function divisible by 8

1. Mar 19, 2014

### Panphobia

1. The problem statement, all variables and given/known data
Prove if n is an odd integer then n^2 - 1 is divisible by 8

3. The attempt at a solution
I already set up the whole inductive step and everything but I am trying to prove it works for n+1, here is what I have so far...
n=2k+1
((2k+1)+1)^2 - 1 = 4k^2 + 8k + 3 = 8m
Where k and m are arbitrary integers.
What do I do from here to get it in the form 8m? I can't figure it out.

2. Mar 19, 2014

### SammyS

Staff Emeritus
2k+1 is an odd integer.

The next odd integer is 2(k+1)+1 = 2k + 3 .

Last edited: Mar 19, 2014
3. Mar 19, 2014

### Panphobia

Then it's 4k^2 + 12k + 8 ...that whole function can't be put in the form 8m as I see it there

4. Mar 19, 2014

### SammyS

Staff Emeritus
Do you know how to do an inductive proof ?

5. Mar 19, 2014

### Panphobia

I know how to do an inductive proof in some settings, but ones like this, not really. In class my professor did something with a similar question, he added the most random term, then subtracted it, and everything worked out. But I can't figure out what to do for this one.

6. Mar 19, 2014

### SammyS

Staff Emeritus
What do you assume for the inductive step?

7. Mar 19, 2014

### Panphobia

For all k in 0..(+infinity) ((2k+1)^2 -1) mod 8 = 0

8. Mar 19, 2014

### SammyS

Staff Emeritus
If it's true for all k, then there's nothing to prove.

Assume that for some positive integer k, ((2k+1)^2 -1) mod 8 = 0 .

Of course that means that there is an integer, m, such that ((2k+1)2 -1) = 8m​

Now with that assumption, you need to show that it follows that ((2k+3)^2 -1) mod 8 = 0 .

Right ?

9. Mar 19, 2014

### Panphobia

Yea, I understand all of that. Am I supposed to use P(2k+1), in some way with P(2k+3), where P(2k+1) is the unary predicate, "((2k+1)^2-1)"

Last edited: Mar 19, 2014
10. Mar 19, 2014

### Panphobia

I think I figured it out, so we assume that P(2k+1) is true, so to prove P(2(k+1)+1), P(2k+1) has to show up somewhere, since P(2k+1) is defined as 4k^2 + 4k = 8m that means P(2(k+1)+1) = 4k^2 + 12k + 8 = 4k^2 +4(3k+2), which is in the form, 4k^2 + 4k, so is that proof enough?

11. Mar 19, 2014

### Dick

No, but you're getting warmer. You have 4k^2+4k is divisible by 8. Now you want to conclude 4k^2+12k+8 is also divisible by 8. What's the difference between the two?

12. Mar 19, 2014

### Curious3141

Do you need to use induction? This is actually very easy to prove without it.

13. Mar 19, 2014

### Panphobia

Oh my...it was staring at my the entire time, split up the 12k, so its 4k^2 + 4k + 8k + 8, by definition 4k^2 + 4k is divisible by 8, but 8k + 8, is also divisible by 8. I am 99% sure this is the right answer.

14. Mar 19, 2014

### Dick

I'm 100% sure.

15. Mar 19, 2014

### Panphobia

Thanks alot, now I know exactly what I am supposed to do in induction.

16. Mar 19, 2014

### Dick

Yeah, separate the part you know is true from the induction hypothesis from the part you don't know does and show the combination is true.

Last edited: Mar 19, 2014
17. Mar 20, 2014

### Staff: Mentor

"((2k+1)^2-1)" is not a predicate, unary or otherwise.

18. Mar 20, 2014

### Panphobia

Well then obviously my professor has been mistaken, because that was the exact line from a slide he had.

19. Mar 20, 2014

### Staff: Mentor

I should add that in your other thread about proofs by contradiction, you said "prove a statement like $\sqrt{2}$ by contradiction". You are not using the terms statement and predicate correctly. Whatever textbook you're using should have definitions of these terms.