Mathematical induction/Talk

Can I make the following suggestion? The reasons for the changes are as follows

1. 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)
2. 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:

1. Showing that the statement holds for the number 0.
2. 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