Printable View
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.
No, it does not mean that.Quote:
Originally Posted by Keysle
Ifis an odd integer, then
is an even integer and hence divisible by two.
Sois an integer. Thus
.
Thereforeis a particular integer.
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.
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").
Thanks. This helps wrap my head around the proof process.