Is This Proof That 8 Divides n^2 - 1 for Odd n Valid?

In summary: assume this to be true), which we can rewrite as 8|2(2(2k^2+2k)+1), which is true because 8|2k^2+2k.

Homework Statement

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

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.

Found my logic wrong. Closing this thread.

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.

Delta² said:
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 :)

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.

QuantumQuest, r0bHadz, SammyS and 1 other person
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?

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.

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|n2 - 1
3. Now show that for n = k + 2, the statement is also true. Do this by substituting n = k + 2 in the expression n2 - 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

Last edited:
Mark44 said:
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|n2 - 1
3. Now show that for n = k + 2, the statement is also true. Do this by substituting n = k + 2 in the expression n2 - 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?

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

Delta² said:
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.

Delta2

1. What does the statement "8|(n^2 -1) for n odd" mean?

This statement means that when n is an odd number, the result of n squared minus 1 will be divisible by 8.

2. How can we prove this statement?

We can prove this statement using mathematical induction. This involves showing that the statement is true for the base case (when n=1) and then assuming that it is true for some arbitrary value of n and using this to show that it is also true for n+2. This process can be repeated until we have shown that the statement is true for all odd values of n.

3. Can you give an example to illustrate this statement?

Sure, let's take n=3 as an example. Then n squared minus 1 is equal to 8, which is divisible by 8. This shows that the statement holds true for n=3.

4. Why is it important to prove this statement?

Proving this statement is important because it helps us to understand the properties of odd numbers and their relationship to the number 8. This can also be useful in solving more complex mathematical problems that involve odd numbers.

5. Are there any real-world applications of this statement?

Yes, this statement has applications in various fields such as computer science, engineering, and physics. For example, it can be used in coding algorithms, designing circuits, and analyzing patterns in natural phenomena.

Replies
6
Views
1K
Replies
6
Views
1K
Replies
9
Views
2K
Replies
3
Views
1K
Replies
10
Views
702
Replies
4
Views
949
Replies
19
Views
745
Replies
4
Views
312
Replies
12
Views
2K
Replies
4
Views
1K