# Monthly Archives: April 2012

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

## Largest prime number ever know !

The largest prime number till found in

2^{43112609} – 1 ( mersenne primes )

This number was discovered by G1 year 2008 . This number has total of 12978189 digits . Landon Curt Noll computed the decimal value of this prime with calc and the English name with number.

Here is the top 10 mersenne primes known

rank | prime | digits | who | when | reference |
---|---|---|---|---|---|

1 | 2^{43112609}-1 |
12978189 | G10 | 2008 | Mersenne 47?? |

2 | 2^{42643801}-1 |
12837064 | G12 | 2009 | Mersenne 46?? |

3 | 2^{37156667}-1 |
11185272 | G11 | 2008 | Mersenne 45? |

4 | 2^{32582657}-1 |
9808358 | G9 | 2006 | Mersenne 44? |

5 | 2^{30402457}-1 |
9152052 | G9 | 2005 | Mersenne 43? |

6 | 2^{25964951}-1 |
7816230 | G8 | 2005 | Mersenne 42? |

7 | 2^{24036583}-1 |
7235733 | G7 | 2004 | Mersenne 41 |

8 | 2^{20996011}-1 |
6320430 | G6 | 2003 | Mersenne 40 |

9 | 2^{13466917}-1 |
4053946 | G5 | 2001 | Mersenne 39 |

10 | 2^{6972593}-1 |
2098960 | G4 | 1999 | Mersenne 38 |

THANK YOU !

## Matrices

In today’s blog, I will review some very basic results in 2×2 and 1×2 matrices.

1. Matrix defined

A matrix is a grouping of numbers that allows working on all the numbers at the same time.

For example, let’s consider a 2 x 2 matrix that can be based on a set of numbers: 1, 2, 3, 4.

The matrix itself looks like this:

2. Addition and subtraction of matrices

Addition and subtraction of matrices are exactly the same as if you added and subtracted the numbers independently:

3. Multiplication of Numbers with Matrices

Multiplication with an integer just applies the integer to all the values involved so that:

4. Product of Two Matrices

In addition to these properites, matrices have there own special operations. The product of 2 matrices is a bit confusing. We define a product of a 1 x 2 matrix with a 2 x 2 matrix as the following:

We define a product a 2 x 2 matrix with a 2 x 2 matrix as the following:

Now, here’s where it gets a bit confusing. We normally refer to a matrix using a capital letter. So let’s say we have two matrices A,B such that: A is a 2×2 matrix and B is a 2×2 matrix. We cannot assume that AB = BA. For example, if we reverse the matrices above, we get the following equation:

Another important point is that there is no product defined for a 2×1 matrix and a 2×2 matrix or a2x2 matrix and 1×2 matrix (since order is important in matrix products) and for that matter, there is no product defined a 2×2 matrix with a 1×2 matrix. In the case of 2×2 matrices, you can only get a product for a 2×2 matrix with a 2×2 matrix or a 1×2 matrix with a 2×2 matrix.

5. Determinant

A determinant is a value that is derived from a 2×2 matrix. Here is the definition:

Lemma 1: det(AB) = (detA)(detB)

(3) det(AB) = (ae+bg)(cf+dh) – (af+bh)(ce+dg) = (acef + adeh + bcfg + bdgh) – (acef + adfg + bceh + bdgh) = adeh + bcfg – adfg – bceh.

(4) det(A) = ad – bc

(5) det(B) = eh – fg

(6) So det(A)det(B) = (ad – bc)(eh – fg) = adeh + bcfg – adfg – bceh

QED

6. Identity Matrix

The Identity Matrix is referred to as I and defined as:

Lemma 2: AI = IA = A

QED

7. Inverse

We denote the inverse of A as A^{-1} and we define it as:

A^{-1} =

Lemma 2: AA^{-1} = A^{-1}A = I

QED

Lemma 3: det A^{-1} = 1/(det A)

(1) (det A)(det A^{-1}) = det(AA^{-1}) [From Lemma 1]

(2) det(AA^{-1}) = det(I) [From Lemma 2]

(3) det(I) = 1*1 – 0*0 = 1. [Definition of I, Definition of Determinant]

(4) So, (det A)(det A^{-1}) = 1

(5) And dividing both sides by (det A) gives us:

det A^{-1} = 1/(det A)

QED

7. Final Points

The last point here is that while AA^{-1} = I, it is not necessarily true that ABA^{-1} = B. The reason is that AB does not necessarily equal BA and we are not allowed to change the order of the matrix elements.

You are free to ask your doubts here : Click here

Thank you !

## Fractions

A fraction is any ratio between whole numbers. In mathematical terms, it is called a rational number. An irrational number is any number such as π which cannot be represented as the ratio of two whole numbers. 🙂 🙂

In today’s blog, I will go over a single lemma regarding fractions:

Lemma: for any given rational number let’s say a/b, there exists an integer let’s say c such that: absolute (a/b – c) ≤ (1/2).

(1) To prove this, we need only consider the case where abs(a) is greater abs(b). [If abs(a) ≤ abs(b), then the conclusion follows from Corollary 2.1, here]

(2) From the division algorithm (see Theorem 1, here), we know that a = bq + r where r ≥ 0 and less than abs(b).

[For example, if a=-3, b=-2, then q=2, r=1 where r is greater than b but less than abs(b).]

(3) Let a’=abs(a), b’=abs(b)

(4) We know that a’ – b’q is less than b’ (since a’ – b’q = r and r is less than b’)

(5) So, it follows that: a’/b’ – q is less than 1.

(6) Now, if both a,b are positive or a,b are negative, it follows that a/b = a’/b’ and abs(a/b – q) is less than 1.

(7) If a,b are of different sign, than -a/b = a’/b’ and -a/b – q = -(a/b + q) so that abs(a/b + q) is less than 1.

(8) The conclusion follows from Lemma 2, here.

QED

Corollary: if a/b is a rational number, then there exists an integer c such that: absolute(a/b – c/2) ≤ (1/4).

(1) From the lemma above, we know that for 2*(a/b), there exists a number c such that:

abs(2*(a/b) – c) ≤ (1/2).

(2) Dividing both sides by 2, gives us:

abs(a/b – c/2) ≤ (1/4)

QED

Now, it turns out that any number with a repeating decimal can be represented as a rational number.

Let me start with an example

(1) Let’s assume that we have a decimal such as 5.234523452345… We can represent this decimal as a repeating decimal such as 5.2345.

(2) Now, we know if we multiply the number by 104 we get:

52345.2345

(3) So, subtracting (2) by (1) gives us:

104 – 1 = 52345 – 5 = 52340.

(4) So, the rational form of this repeating decimal is:

52340/9999.

Now, let’s look at the proof that demonstrates this:

Lemma: Any number with a repeating decimal is rational.

(1) Any number with a repeating decimal can be represented with the following form:

d1…dm.a1…an

NOTE: If a number has a nonrepeating portion, then we multiply this number by the number of nonrepeating digits, to get a number of the above form. Later, we divide our result by this same number.

(2) We can get an integer result by subtracting 10n*the number by the original number which after canceling for the repeating decimal gives us:

10n * (d1…dm.a1…an…) – (d1…dm.a1…an…) =

(d1..dma1..an) – (d1..dm).

(3) Now, our rational number is equal to the value in step #2 divided by 10n – 1.

QED

THANK YOU !