# Category Archives: Mathematical Induction

## 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