Proving 8|(n^2 -1) for n odd

[r0bHadz]

Homework Statement

If n ∈ ℤ^+ and n is odd, prove 8|(n^2 -1)

Homework Equations

The Attempt at a Solution

n = 2b+1 for b ∈ ℤ^+ by the definition of positive odd int

n^2 = (2b+1)(2b+1) = 4b^2+4b+1 = 2(2b^2+2b) + 1

n^2 - 1 = 2(2b^2+2b) so n^2 - 1 will be even ∀n s.t n is odd

For n = 1, 8|0 is true, for n=3, 8|8 is true

If n ≥3, n^2 - 1 ≥ 8, and since n^2 -1 will always be even, n^2 -1 will always be able to be divided three times by 2, thus 8 | n^2 -1

I don't want an answer. If you post an answer please put a spoiler so I can know not to read it. Can someone just tell me if this proof is valid or not?

To me, it makes sense. Since n^2 - 1 will be greater than 8 for n>3, and 8 is 2^3, and since n^2 - 1 is an even number which means it is divisible by 2, since it is greater than 8 it will be divisible by 2 at least 3 times.

 

[r0bHadz]

Found my logic wrong. Closing this thread.

 

[Delta2]

I agree your logic was wrong (for example the number 34 is even, greater than 8 but it is divisible by 2 only one time), but you almost have this. Just prove with induction on b, that the number 2(2b^2+2b) is a multiple of 8.

 

[r0bHadz]

I agree your logic was wrong (for example the number 34 is even, greater than 8 but it is divisible by 2 only one time), but you almost have this. Just prove with induction on b, that the number 2(2b^2+2b) is a multiple of 8.

Well it wouldn't be nice to just abandon this thread without my next answer so here goes, let me know what y'all think:n = 2b+1 for b ∈ ℤ^+ by the definition of positive odd int

n^2 = (2b+1)(2b+1) = 4b^2+4b+1 = 2(2b^2+2b) + 1

n^2 - 1 = 2(2b^2+2b) so n^2 - 1 will be even ∀n s.t n is odd

For n = 1, 8|0 is truelet s(k) : 8 | 2(2k^2+2k) for k ∈ℤ^+

assuming s(k) to be true,

show s(k+1) : 8 | 2(2(k+1)^2 + 2(k+1)) 8x = 2(2k^2 +2k)

8x = 4k^2 +4k

8x + 8k + 8 = 4k^2 + 4k + 8k +8

8(x+k+1) = 2(2(k+1)^2 + 2(k+1))

s(k+1) is true, so 8 | n^2 - 1

 

[Delta2]

I think now you are correct :)

 

[Mark44]

Instead of a proof by induction, you can do the proof directly.

Given that n is odd, we can write n = 2k + 1, for some integer k
$n^2 - 1 = (n - 1)(n + 1) = (2k + 1 - 1)(2k + 1 + 1) = 2k(2k + 2) = 4k(k + 1)$
For any integers k and k + 1, one of them will be odd and the other will be even, so the product k(k + 1) is even.

Since the product 4k(k + 1) has a factor of 4, and k(k + 1) is even, then 8 divides 4k(k + 1), and therefore 8 divides $n^2 - 1$ when n is odd.

 

[r0bHadz]

Hmm my teacher brought up a great point, I don't think proof by induction works on this problem.

Look at my third line of my proof 2 posts up

"n^2 - 1 = 2(2b^2+2b) so n^2 - 1 will be even ∀n s.t n is odd"

I wrote "For n = 1, 8|0 is true," but my proof involves statements with the variable b, not n.

I could let s(b): 2(2b^2 + 2b)
and s(1) = 8

but this won't get me anywhere

or I could let s(b): 8| 2(2b^2 +2b)

but how do I know 8| 2(2b^2 +2b) ?? I don't.

So it seems to me like this proof can't be done by induction. Does anyone agree with me here?

 

[Delta2]

Hmm my teacher brought up a great point, I don't think proof by induction works on this problem.

Look at my third line of my proof 2 posts up

"n^2 - 1 = 2(2b^2+2b) so n^2 - 1 will be even ∀n s.t n is odd"

I wrote "For n = 1, 8|0 is true," but my proof involves statements with the variable b, not n.

I could let s(b): 2(2b^2 + 2b)
and s(1) = 8

but this won't get me anywhere

or I could let s(b): 8| 2(2b^2 +2b)

but how do I know 8| 2(2b^2 +2b) ?? I don't.

So it seems to me like this proof can't be done by induction. Does anyone agree with me here?

Induction on n will not work, but you did induction on b(on k actually, for some reason you renamed b to k).

You did a small mistake on the induction step, you should have said that for k=1, 8| (2(2x1^2+2x1) or equivalently 8|8.
And then we take as induction hypothesis that 8|2(2k^2+2k) (we don't need to prove this, this is the induction hypothesis, we have the right to make this hypothesis) or equivalently that 8x=2(2k^2+2k) for some x.

 

[Mark44]

Hmm my teacher brought up a great point, I don't think proof by induction works on this problem.

Look at my third line of my proof 2 posts up

"n^2 - 1 = 2(2b^2+2b) so n^2 - 1 will be even ∀n s.t n is odd"

I wrote "For n = 1, 8|0 is true," but my proof involves statements with the variable b, not n.

I could let s(b): 2(2b^2 + 2b)
and s(1) = 8

but this won't get me anywhere

or I could let s(b): 8| 2(2b^2 +2b)

but how do I know 8| 2(2b^2 +2b) ?? I don't.

So it seems to me like this proof can't be done by induction. Does anyone agree with me here?

An induction proof will work, but you have to limit the numbers n to odd numbers.
1. if n = 1, the statement is true
2. Assume that for n = k, an odd integer, that 8|n² - 1
3. Now show that for n = k + 2, the statement is also true. Do this by substituting n = k + 2 in the expression n² - 1. It's a little tricky to show, but the basic idea is that if you have an odd integer k, then either k + 1 or k + 3 is divisible by 4.
Edit: Corrected an earlier typo

 

[Delta2]

An induction proof will work, but you have to limit the numbers n to odd numbers.
1. if n = 1, the statement is true
2. Assume that for n = k, an odd integer, that 8|n² - 1
3. Now show that for n = k + 2, the statement is also true. Do this by substituting n = k + 2 in the expression n² - 1. It's a little tricky to show, but the basic idea is that if you have an odd integer k, then either k + 1 or k + 4 is divisible by 4.

Induction on n might work but he did induction on b and I think he is mostly correct, cause b is any positive integer (and n=2b+1).

And btw you mean k+3 there right?

 

[PeroK]

The inductive step on $n$ seems quite straightforward:

If $n^2 - 1 = 8k$, then $(n+2)^2 - 1 = n^2 - 1 + 4n + 4 = 8k + 4(n+1)$

And, as $n+1$ is even, we see that $8|((n+2)^2 -1)$

 

[Mark44]

And btw you mean k+3

Yes. In my notes I have k + 3, but managed to hit 4 when I typed it. I fixed it in what I wrote.