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.
Sorry. I meant to put emphasis on the phrase "for an integer k.". For some reason it didn't accept my font alteration.
Well apparently. on this computer it does show up. and now that I'm re-reading your comment. ...
This is awfully confusing.
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
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").