Quote:
Originally Posted by Mariogs379
I suck at induction part 2:
To do a proof by induction I have to have the one-case be true, then assume the general case is true, and prove that the successive case holds. But somehow I'm just awful at this:
want to prove the associative law for addition
(m+n) + k = m + (n+k)
one-case: (m+n) + 1 = m + (n+1) (are we just assuming this is true?)
So, we suppose (m+n) + k = m + (n+k) and must show that (m+n) + (k+1) = m + [n+(k+1)].
But the text starts with: (m+n) + (k+1) = [(m+n) + k] + 1 (by the one-case)...I'm not sure what they mean here by "by the one case"...
Sorry if this is a super basic question but I'm obviously missing something.
Thanks for the help guys,
Mariogs
You have to start your theorem more carefully (I don't even know what setting you're in: R, N, Z, ???). So, for instance, we could say:
Thm: For all natural numbers m, n, k, we have that (m+n) + k = m + (n+k).
Proof: By induction on k. Fix m and n, natural numbers. Let K be the set
{k in N : (m+n) + k = m + (n+k)}. In this proof, we will use two axioms of natural numbers.
(A1): for any a in N, a + 0 = a
(A2): for any a, b in N, (a+b)+1 = a+(b+1)
Now, to the proof. Notice that 0 is in K by (A1); that is, (m+n)+0 = m+n = m + (n+0). Now, since K is nonempty, choose k from K. We'll show that k+1 is also in K.
(m+n) + (k+1) = ((m+n)+k) + 1, by (A2)
....................= (m + (n+k)) + 1 since k is in K.
....................= m + ((n+k) + 1) by (A2)
....................= m + (n + (k+1)) by (A2).
So k+1 is in K. By PMI, then, K = N, and the theorem follows.
Edit: So let's explain induction a bit more carefully. The principle of mathematical induction says that if we have a property that is either true or false for all natural numbers (call it P(n): so maybe P(0) is true, P(2) is false, etc. In our case above, P(k) is true if (m+n)+k = m+(n+k), and we want to show P(k) true for all k in N), then
if P(0) is true AND [ P(k) true => P(k+1) true], then P(k) is true for all k.
You might view induction as dominoes. If you knock down the k_th domino, the (k+1)st one falls. So as long ass you knock down 1 domino, all of the succeeding ones fall. i.e. if we can knock down P(0), and if [ P(k) true => P(k+1) true] (i.e. if knocking down P(k) implies that P(k+1) will fall), then all dominos will fall.
That we started at 0 is arbitrary; in many cases it's right to start at one. I prefer the term "base case" to "one case" for this reason. It's the first domino that gets knocked down.
Last edited by Wyman; 12-10-2009 at 04:35 PM.