I need help understanding the basis of how proof work.

I missed the concept of "proofs" in highschool.

I'm a programmer right now and something tells me they are valuable to my interest in pattern finding.

I was reading this wiki page about basic proofs, but there is something I did not understand.

It's extremely simple, I'm sure, but I don't want to jump to assumptions.

So here it is

"If x is odd (not even) then x = 2k + 1 for an integer k."

Does this mean "make K any integer"? The language used isn't intuitive.

Thanks for any help.

Re: I need help understanding the basis of how proof work.

Quote:

Originally Posted by

**Keysle** I was reading

this wiki page about basic proofs, but there is something I did not understand.

It's extremely simple, I'm sure, but I don't want to jump to assumptions.

So here it is

"If x is odd (not even) then x = 2k + 1 for an integer k."

Does this mean "make K any integer"? The language used isn't intuitive.

Thanks for any help.

No, it does not mean that.

If $\displaystyle x$ is an **odd integer**, then $\displaystyle x-1$ is an even integer and hence divisible by two.

So $\displaystyle k=\frac{x-1}{2}$ is an integer. Thus $\displaystyle x=2k+1$.

Therefore $\displaystyle k$ is a particular integer.

Re: I need help understanding the basis of how proof work.

Sorry. I meant to put emphasis on the phrase "**for an integer k.**". For some reason it didn't accept my font alteration.

edit ----------------

Well apparently. on this computer it does show up. and now that I'm re-reading your comment. ...

...

...

This is awfully confusing.

Re: I need help understanding the basis of how proof work.

it means that there is at least one integer ("labelled" k, since we haven't determined it) with:

x = 2k + 1.

as stated, it could perhaps be that there are many such integers, although this is in fact not the case.

for example, for x = 7, one such k is k = 3 (7 = 2(3) + 1).

in the context of the wikipedia page, this may as well be taken as the definition of "oddness":

an integer x is called odd if there is some other integer k with x = 2k+1. this is just a mathematical way of saying the odd integers are "in-between" the even ones, which are spaced 2 apart.

often, in arguments about "evenness" and "oddness" (parity arguments), we don't need to know what "k" is. when you flip a switch, how many times you've flipped it is irrelevant, all that matters is its parity with the original state (from which you can tell the current state).

given a certain odd integer x, you can use Plato's method to FIND k, if you know x. but if all you know is that x is odd, then k is just a (generic) integer. one can even state this as a theorem:

for all integers k, 2k+1 is odd.

proof (by induction):

first suppose k is a natural number (which i will take as including 0).

for k = 0, 2k+1 = 2(0) + 1 = 0 + 1 = 1. since 1/2 is not an integer, 1 is not divisible by 2, thus 1 is odd (not even).

now suppose that 2k+1 is odd.

if we can prove 2(k+1) + 1 = 2k + 2 + 1 = 2k + 3 is odd, we will have completed the "inductive step".

but 2k + 3 = 2k + 2 + 1, so (2k + 3)/2 = (2k + 2)/2 + 1/2.

if 2k + 3 is even, then (2k + 3)/2 is an integer, and since (2k + 2)/2 = k + 1, which is clearly an integer, we have that:

1/2 = (2k + 3)/2 - (k + 1) is an integer, which is absurd. thus 2k + 3 must be odd (not even), so by the principle of induction, we conclude that 2k+1 is odd, for all natural numbers k.

finally, if k < 0, then k = -m, for some positive integer m, and:

2k + 1 = 2(-m) + 1 = -(2m - 1) = -(2(m-1) + 1).

now m-1 is natural number (since k < 0, -k = m > 0, so m-1 ≥ 0), therefore by our above result: 2(m-1) + 1 is odd.

so we only have to prove the following:

if x is odd, so is -x.

again, suppose -x is even, so -x/2 is an integer. since the negative of an integer is still an integer, x/2 is also an integer, so x is even. but this is absurd, as x is odd. thus -x cannot be even, so must be odd.

the above discussion, together with Plato's post shows that saying:

there exists an integer k such that x = 2k+1

and:

x is an odd integer

are equivalent, each implies the other, and they can be used interchangeably.

one can show easily that the "k" in x = 2k+1 is unique:

suppose x = 2k+1 = 2m+1

then 2k = 2m, so

k = m (multiplication of integers is "cancellative").

Re: I need help understanding the basis of how proof work.

Thanks. This helps wrap my head around the proof process.