Proof by induction

[parksie]

I get the process for this, but not the point :(

I mean,

To prove that sigma(1 to n) {r(r+1)(r+2)} = (1/4)n(n+1)(n+2)(n+3)

Consider n = k+1

sigma(1 to k+1) {r(r+1)(r+2)} = sigma(1 to k) {r(r+1)(r+2)} + (k+1)(k+2)(k+3)

= (1/4)(k+1)(k+2)(k+3)(k+4)

True for n = k + 1, so true for all n is a member of Z+.

It's the last bit I don't get :(

[Guv]

Proof by induction has the following general format. Show by some simple method that theorem is valid for some specific values, like 1, 2, 3 Prove that if true for K,Then it is true for (K + 1). Then: Since is true for 3 (by Step 1), it must be true for 4 (by Step 2) Since true for 4, it must be true for 5(by Step 2 again) Et cetera for 6, 7, 8, ....The step missing in your post is showing or proving it is true for say 1, 2, & 3.

[parksie]

Ahaaaaaa.....


Thanks m8 :D

[Balder]

I´m impressed Guv, you must have been around for a while :)

[samwise]

Lets consider a proof by induction case, as this.

Theorm : All sets have elements that are equal to all other elements in that set.

(for short hand, we use #S for number of items in a set)

Proof by Induction :

First, we prove it works for sets where #S = 1


Proof: Well, there is only one element in a set.
For element x of set S, we know that x = x.
Therefore, it works for #S=1


Second, we assume it works for #S=N, N>1, and prove it works for #S=N+1.

Proof: We have a set S such that #S=N+1.
We take out one element of the set, such that this set S has #S=N.
We know that all elements are equal (because we assume #S=N works, remember?)
We put that element back into the set, and take out a different element.
We know that all elements are equal (because we assume #S=N also works).
We can repeat this process for all elements in the set S.
We can now conclude that all of the elements are equal, and therefore, the proof works for #S=N+1.

Since I have proved it works for #S = 1, and have shown that #S=N implies #S=N+1, therefore all sets with N elements have identical elements.

Can you catch the bug?

Samwise Galenorn
sam@galenorn.com

[Guv]

Samwise: Your proof is interesting. Every time I used proof by induction, I verified the proposed theorem for several values, usually 1, 2, & 3. Obviously, your theorem cannot be verified for all possible sets with 2 or 3 elements. A simple counter example can be used to disprove it for sets with 2 or 3 elements. This observation is sufficient to invalidate your proof, but does not seem to be the entire story.

When I first read your post, I tried to refresh my memory on proof by induction by consulting a mathematical text I had handy. It had a chapter relating to proof by induction applied to properties and theorems relating to the set of positive integers. In that text, verification for N = 1 seemed to be sufficient for proving theorems relating to integers.

The second part of your proof seems superficially valid for proving the theorem true for N = 2, which seems absurd due to the ease of a disproof by counter example.

The above makes me wonder a bit. Is proof by induction okay for the set of integers verifying only for N = 1, but otherwise requires verification for more values?

Note that part of a proof by induction assumes that the theorem being proved is valid for a value N, and then using this assumption attempts to prove that it is valid for (N+1). Is there some logical trap if induction is used to prove an inherently invalid theorem? I remember from somewhere that you can prove anything if you start with mutually exclusive axioms.

It would seem that all the above problems can be bypassed by requiring verification for several values before continuing with a proof by induction. Still the mathematical text did not require this for proofs relating to the set of all integers.

Comments anybody?

[samwise]

"Second, we assume it works for #S=N, N>1, and prove it works for #S=N+1."

I didn't mean to state 'N>1'. That gives away the flaw. Sorry.

Samwise Galenorn
sam@galenorn.com