# Mathematical Induction

I love this topic 😀

Mathematical induction is a method for proving a condition is true of an infinite set that obeys the well-ordering principle.

A set is considered well-ordered if for any subset of elements, one can always find one element which is the smallest. An example of a well-ordered set is the set of positive integers. One element is clearly the smallest. For example, if 1 is an element in the set, then it will be the smallest element.

Not all sets are well-ordered. For example, negative integers are not well-ordered. In such an infinite set, there is never one element which is the smallest. Likewise, real numbers are not a well-ordered set. For any number, it is possible to find another number which is smaller if only by a fraction. There is no smallest value.

It is useful to introduce some notation when talking about well-ordered sets. Sets are often refered to as capital letters such as S, T, R. Elements are often refered to as lowercase letters such ass,t,r.

We can imagine that s is an element of S, t is an element of T, and r is an element of R. Likewise, we can use a subscript to differentiate elements so that s_{1}, s_{2}, etc. are all elements of S. t_{1}, t_{2}, etc. are all elements of T.

When talking about induction, we are always trying to prove some proposition true about an entire set. When talking about a proposition or fact, I will use the following form p(). So, for example,p(s_{1}) means that the proposition is true of the first element of the set S. Likewise p(S) means that the proposition is true of all elements of set S.

Finally, I need to use the concept of implication which is symbolized by →. Implication doesn’t say something is true or false. Rather, it describes a relationship. If a certain condition is true, then another condition follows. If I were president, I would be living in India . This doesn’t mean that I am president and it doesn’t mean that if I am living in India ., then I am the president. It simply means that if the first condition were true (if I were the president), then the second condition would follow (then I would live in India ).

With this notation, I can now state the **Principle of Mathematical Induction:**

Theorem: Principle of Mathematical Induction: if p(s_{1}) is true and if p(s_{n}) → p(s_{n+1}), then p(S).

(1) Let’s start by assuming that the theorem is false.

(2) Let’s let s_{i} be the first element in order where p(s_{i}) is not true.

(3) Well i cannot be the first element since we are assuming that p(s_{1}) is true.

(4) So, this means that p(s_{i-1}) must be true since i is the first element where the proposition is not true.

(5) But if p(s_{n}) is true, then p(s_{n+1}) is true, so therefore p(s_{i}) must be true since p(s_{i-1}) is true.

(6) But this is a contradiction so we reject (1) and conclude that the theorem is true.

QED

In next post we will do some basic problems on Induction and concrete this concept in mind , as it is a bit useful tools provided by mathematics to prove something !! 😀 😀 😀

THANK YOU 🙂

You can ask your doubts on any topic ( Don’t feel shy in asking 😀 ) : Click here

Posted on Friday,April 6, 2012, in Mathematical Induction and tagged induction, nice, problem solving, tools, well ordering principle. Bookmark the permalink. 5 Comments.

Great , Fantastic !

Thanks , share the page ! If you like it !

Nice ……assidous

awesome

thanks Aayush kumar 🙂 🙂

I find this topic fascinating and I like it a lot too, I warmly recommend to read “The Logical Leap: Induction in Physics” by David Harriman, look for it in Amazon or so.

Behind the mathematical formalism of induction, there is an amazing quantity of philosophy -specially at Epistemology level, that makes Induction the only valid form to gain knowledge. I mean “gain” as from starting from zero, not “learning” what somebody already discover before you. One thing that hit me is the idea: induction is not merely enumeration. You know, usually we deal with enumeration so we tend to confuse both. Induction is actually a conceptual integration, an abstraction made from a number of concretes.

The book is oriented to physics but you will enjoy it as well, as it put forward the idea of “knowledge algebra”. You know: when you see the concept “orange” you understand is not only an specific orange, but also every orange you saw in the past is associated to this concept, every orange in history and all the orange you will see in the future. SO, “Orange” as a meaningful concept is actually algebraic: it encloses a quantity -but also any quantity- of concretes, so you won’t be helpless when you meet a new orange. You don’t invent a new concept for every new orange, you already have a concept integrated in your mind.

Induction and knowledge algebra are quite related, and the book opens your eyes in that respect. Recommended!