Talk:Mathematical induction
|
|
This is my first visit to this website. It is amazing. I've never seen anything this great on the internet.
My request: Can you guys put up some more example problems and solutions? It would really be great for CS and Math majors.
Can I make the following suggestion? The reasons for the changes are as follows
- I want to include 0 with the natural numbers. (The "first n integers", by the way, is not really correct since the integers also contain negative numbers)
- the notation A= {Ai: i=1,2,3,...,n} is not trivial. I know that you are building a proposition here by taking the conjunction of an infinite number of propositions, but I am not sure if that is immediately clear to anyone. So below is my suggestion. -- Jan Hidders
- Replacing a well understood word like proposition with a jargon word like "predicate" reduces understanding.
- Both notations {Ai:...} and P(n) aren't necessary. Basic concepts like induction need to be described in common, non technical, language, or the lay reader will never learn anything.
I'm not so sure that the term proposition is not jargon. It doesn't look like it but it has a quite specific meaning in logic. But I agree that everything should be as jargon free as possible. So I've adapted my version below a little. Let me know what you think. And, as usual, if you think some more explanation should be added, please do. -- JanHidders
Mathematical induction
Mathematical induction is the standard way of proving that a certain statement about a number n holds for all natural numbers. Such a proof consists of two steps:
- Showing that the statement holds for the number 0.
- Showing that if the statement holds for a number n then the same statement also holds for n + 1.
Heres an alternative version of the example, which I think is easier for the lay reader... Comment? GWO
Yes, better. Although I would like to have spaces around '+' and '='. And I'm wondering why you don't change the definition in a similar way. Then you get "showing that the statement holds for n = 0" and "showing that if the statement holds for n = m then the same statement also holds for n = m + 1. -- JanHidders
Re: Spaces. You're right, and I think you're right about the definition too. Do you want to make the changes on Mathematical induction itself? GWO
I will do it. Thank you for helping. -- JanHidders
Example:
Suppose we wish to prove the statement that the sum of the first n natural numbers, that is 1 + 2 + 3 + ... + n, is equal to n(n + 1)/2.
The proof that the statement is true all natural numbers proceeds as follows:
- (1) Check it is true when n=0. Clearly, the sum of the first 0 natural numbers is 0, and 0(0 + 1)/2 = 0. So the statement is true when n=0.
- (2) We have to show that if the statement holds when n=m, then it holds when n=m+1. This can be done as follows.
- Assume the statement is true for n=m holds, i.e.,
m(m + 1)
1 + 2 + ... + m = --------
2
- Adding m + 1 to both sides gives
m(m + 1)
1 + 2 + ... + n + (m + 1) = -------- + (m + 1)
2
- By algebraic manipulation we have
m(m + 1) 2(m + 1) (m + 2)(m + 1)
= -------- + -------- = --------------
2 2 2
- Thus we have
((m+1))((m+1)+1)
1 + 2 + ... + (m + 1) = ----------------
2
- So the statement is true for n=m+1.
- (3) By induction we conclude that the statement holds for all natural numbers n.
Your version
Example:
Let P(n) be the statement that the sum of the first n natural numbers, that is 1 + 2 + 3 + ... + n, is equal to n(n + 1)/2. The proof that shows that P holds for all natural numbers proceeds as follows.
- (1) P(0) says that the sum of the first zero natural numbers equals 0(0 + 1)/2. This is true since 0(0 + 1)/2 = 0.
- (2) We have to show that if P(n) holds then also P(n + 1) holds. This can be done as follows.
- Assume that P(n) holds, i.e.,
n(n + 1)
1 + 2 + ... + n = --------
2
- Adding n + 1 to both sides gives
n(n + 1)
1 + 2 + ... + n + (n + 1) = -------- + (n + 1)
2
- By algebraic manipulation we have
n(n + 1) 2(n + 1) (n + 2)(n + 1)
= -------- + -------- = --------------
2 2 2
- This shows that P(n + 1) holds:
(n + 2)(n + 1)
1 + 2 + ... + (n + 1) = --------------
2
- (3) By induction we conclude that P(n) holds for all natural numbers n.
I'm wondering if this definition of "mathematical induction" applies to the proofs by mathematical induction that I remember doing in logic. --LMS
Well it certainly should do ... what do you remember about them? GWO
The term is often generalized to not just the natural numbers but anything that is countable. So you can prove something for all integers greater than 6 or for every string that is described by a certain syntax. Sometimes the schema is generalized to (1) prove for n=0 (2) show that if it holds for all m <= n then it holds for n+1. All those generalizations can be reformulated so that they fit the current definition, but that is something that probably needs a little explaining. Is that what you mean? -- JanHidders
That is precisely what I mean, Jan, thanks. Essentially, mathematical induction is a way of making a proof recursive, which is something that is used in logic when the proofs are not about numbers per se. --LMS
I have removed the "proof" of mathematical induction, which I believe to be only slightly better than the "domino effect" argument. The principle of mathematical induction is always stated as an axiom (e.g. Peano's system), a proof seems to be unnecessary. --Wshun
Someone has put down the following three terms:
- Proof of method Mathematical induction is taught in schools, and most students learn it by rote without fully understanding how it works. It is possible to base a proof of mathematical induction on other mathematical principles.
But one of those mathematical principles is EQUIVALENT to the principle of mathematical induction!
- Related methods An induction variant is used in computer science to prove that expressions which can be evaluated are equivalent, and this is known as structural induction.
Hmm, the related article is not wikified. Anyway, it could be put back later.
- Alternative Formulations An alternative formulation of the principle of mathematical induction is the Well-Ordering Principle, which states that any nonempty set of natural numbers must have a smallest element. This principle is equivalent to mathematical induction, as follows:
- Suppose that the well-ordering principle is true, and that the conditions of the proof by induction are true, namely, that for some property P, we know that P(0) is true, and that if P(n) is true for any natural number n, then P(n+1) is also true. We wish to prove that P(n) is true for all natural numbers n. Let S be the set of natural numbers for which P is not true. Let us suppose that S has a smallest element, say m. m cannot be 0, because P(0) is true by hypothesis. So m-1 is a natural number, and in particular m-1 is not an element of S, because m is the smallest element of S. So P(m-1) is true, and by hypothesis P(m) is also true, and we have a contradiction. Thus we conclude that S has no smallest element, and so by the well-ordering principle, S must be empty. P(n) therefore holds for all natural numbers n.
- Conversely, we can prove the well-ordering principle inductively. Let S be a set of natural numbers. We want to prove that either S has a smallest element or else that S is empty. Let P(n) be the statement that no element of S is smaller than n. P(0) is certainly true, since there is no natural number smaller than 0. Suppose that P(n) is true for some n. If P(n+1) were false, then S would have an element smaller than n+1, but it could not be smaller than n, because P(n) was true, and so S would have a minimal element, namely n, and we would be done. So P(n) implies P(n+1) for all n, or else S has a minimal element. But if P(n) implies P(n+1) for all n, then by induction we know that P(n) is true for all n, and therefore for all n, no element of S is smaller than n. But this can only be vacuously true, if S has no elements at all, since every natural number is smaller than some other natural number. Thus we are done.
- An analogous proof holds for any well-ordered set; see transfinite induction.
Is it too technical to be placed on Wikipedia?
--wshun 04:21, 10 Aug 2003 (UTC)
- Regarding only the Alternative Formulations section: I didn't think it was too technical when I put it in. I also think it would be illuminating for a certain audience---people who are familiar with the idea of induction, but who haven't studied set theory yet. It seems strange to me that you decided to remove this section when you yourself weren't sure if it should be removed.
- --Dominus 06:46, 10 Aug 2003 (UTC)
- Oh, it is my strange style :P I like to remove materials that I am not sure if they should be added to the article. BTW, now we have proof of mathematical induction and three forms of mathematical induction, we can move something here and there to reduce redundance. -- wshun 23:23, 10 Aug 2003 (UTC)
Nothing is too technical for Wikipedia provided all the necessary prerequisites are also on Wikipedia! Phys
This section looks odd to me: Proofs by transfinite induction typically need to distinguish three cases:
- m is a minimal element, i.e. there is no element smaller than m
- m has a direct predecessor, i.e. the set of elements which are smaller than m has a largest element
- m has no direct predecessor, i.e. m is a so-called limit-ordinal
The first point says there is no element < m, yet the second implies there is a element smaller than m. Also, the third one contradicts the second: "m has a direct predecessor'", "m has no direct predecessor"
- Of course they contradict each other; that's why they are distinct cases that are distinguished from each other!! Michael Hardy 00:42, 30 Mar 2005 (UTC)