Induction, proving function divisible by 8

[Panphobia]

Homework Statement

Prove if n is an odd integer then n^2 - 1 is divisible by 8

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.

 

[SammyS]

Homework Statement

Prove if n is an odd integer then n^2 - 1 is divisible by 8

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.

2k+1 is an odd integer.

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

 

[Panphobia]

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

 

[SammyS]

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

Do you know how to do an inductive proof ?

 

[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.

 

[SammyS]

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.

What do you assume for the inductive step?

 

[Panphobia]

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

 

[SammyS]

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

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)² -1) = 8m​

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

Right ?

 

[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)"

 

[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?

 

[Dick]

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?

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?

 

[Curious3141]

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

 

[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.

 

[Dick]

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.

I'm 100% sure.

 

[Panphobia]

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

 

[Dick]

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

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.

 

[Mark44]

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)"

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

 

[Panphobia]

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

 

[Mark44]

From the wikipedia page on Predicates (http://en.wikipedia.org/wiki/Logical_predicate)

Informally, a predicate is a statement that may be true or false depending on the values of its variables.[1] It can be thought of as an operator or function that returns a value that is either true or false.

Mathematically, (2k + 1)² - 1 is an expression that has a value that depends on the value of k. It is not a statement that is either true or false. An example of a statement might be something like "(2k + 1)² - 1 is divisible by 3".

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.