# Thread: Proof by cases or "if and only if"?

1. ## Proof by cases or "if and only if"?

The statement is: "Let n be an odd integer. Show that there is an integer k such that n^2 = 8k + 1."

I'm not sure where to begin. I'm thinking that this statement would be equivalent to saying "n is an odd integer iff there is an integer k such that n^2 = 8k + 1." The only other choice is Proof by Cases (based on the section of the book it is in). Once I know where to start, I'm pretty sure I can do the proof, it's just getting started that is my problem.

2. Ok, I just realized that the book gives a hint saying, "Since n is odd, there exists an integer u for which n = 2u + 1. There are now two cases, depending on whether u is even or odd."

So, I started out by saying:

(I re-stated the hint) We proceed by cases.
Case 1: Assume u is even. Then, there exists an integer k for which u = 2k. So, n = 2u + 1 = 2(2k) + 1 = 4k + 1. So, n^2 = (4k + 1)^2 = 16k^2 + 8k + 1.

I see the 8k + 1 part, which is what I will need, but the 16k^2 part is throwing me off on what I do from here. Any help would be appreciated.

3. Oh! Nevermind, I think I figured it out! The next step would be 8k(2k + 1) + 1, where 2k + 1 is an integer.

And then, of course, I'd move on to the second case.

Is this correct?

4. Originally Posted by Lprdgecko
Ok, I just realized that the book gives a hint saying, "Since n is odd, there exists an integer u for which n = 2u + 1. There are now two cases, depending on whether u is even or odd."

So, I started out by saying:

(I re-stated the hint) We proceed by cases.
Case 1: Assume u is even. Then, there exists an integer k for which u = 2k. So, n = 2u + 1 = 2(2k) + 1 = 4k + 1. So, n^2 = (4k + 1)^2 = 16k^2 + 8k + 1.

I see the 8k + 1 part, which is what I will need, but the 16k^2 part is throwing me off on what I do from here. Any help would be appreciated.
Well, you used the letter "k" a little prematurely..

If you let u = 2m, then we have n^2 = 16m^2 + 8m + 1 = 8(2m^2 + m) + 1. Let k = 2m^2 + m.

Just a side note.. this is pretty trivial with modular arithmetic, which you may learn later on.

5. Originally Posted by undefined
Well, you used the letter "k" a little prematurely..

If you let u = 2m, then we have n^2 = 16m^2 + 8m + 1 = 8(2m^2 + m) + 1. Let k = 2m^2 + m.

Just a side note.. this is pretty trivial with modular arithmetic, which you may learn later on.
Thank you. I wasn't sure if I should use "k" at the start or a different variable.