# Homework Help: A little question about a proof

1. Aug 2, 2013

### press

1. The problem statement, all variables and given/known data

Use math induction and cases to prove that every integer is even or odd.

3. The attempt at a solution

Let p(n): n is even or is odd.
Let n be an integer. Assume p(n) is true.
Then n is even or n is odd.

Case 1: Assume n is even. Then n = 2k for some integer k. So n + 1 = 2k + 1. Thus n + 1 is odd.
So, n + 1 is odd or n + 1 is even.
Hence, p(n + 1) is true.
Case 2: Assume n is odd.Then n = 2k + 1 for some integer k. So n + 1 = 2(k + 1). Thus n + 1 is even.
So, n + 1 is even or n + 1 is odd.
Hence, p(n + 1) is true.
In either case, p(n + 1) is true. So, p(n) => p(n + 1)

-------------------------------------------------------------

I copied it from the back of my book. My question is how do we know n + 1 might also be even in Case 1 before we did Case 2? Is there a logical reason for that or is it just stylistic? I am inclined to re-write this proof like this below:

....

Case 1: Assume n is even. Then n = 2k for some integer k. So n + 1 = 2k + 1. Thus n + 1 is odd.

Hence, p(n + 1) is true

Case 2: Assume n is odd.Then n = 2k + 1 for some integer k. So n + 1 = 2(k + 1). Thus n + 1 is even.

Hence, p(n + 1) is true

So, n + 1 is even or n + 1 is odd.

In either case, p(n + 1) is true. So, p(n) => p(n + 1)

------------------------------------------------------

I am reasoning like this:

p or q

Case 1: Assume p

....

Therefore r

Case 2: Assume q

....

Therefore, s.

Therefore r or s.

------------------------------------------
Please, tell me where I am tripping up.

Thanks.

Last edited: Aug 2, 2013
2. Aug 2, 2013

### verty

It is a logical truth that A => A or B. The proof doesn't need it though, it is sufficiently obvious to be omitted.

3. Aug 2, 2013

### junaid314159

They are just being very precise in their proof. The statement p(n+1) means that n+1 is even or is odd. In Case 1, once you show that n+1 is odd, they want to make it extra clear that you have indeed shown that p(n+1) is true by explicitly stating it precisely: n+1 is even or is odd. Note that this is the actual exact statement of p(n+1). Then they follow it with: Hence, p(n+1) is true. They are not trying to say that p(n+1) might be even. They are including it though to match the structure of the original statement you are trying to prove. As verty stated, it is obvious enough so as to be omitted.

Junaid Mansuri