MATHS - 7.INDUCTION

Mathematical Induction :

This is a well taught and useful method at intermediate or even school level to prove certain formulae for sum of a series etc. The method is as follows.

Generally,we are given a series with n terms and given a formula to prove that its sum is given by that formula.

The method of proof is ,

1. we test the formula for applicability in the case of n=1 OR 2 OR WHATEVER IS RELEVANT TO THE PROBLEM .
2. After verifying that it is applicable , we assume that the formula is correct for n = k say , that is for any particular value of “n”.
3. Next we go on to prove that , if it is true for n = k, then , it is also true for n = k + 1 .
4. Now we reason out that since we proved its validity at n = 1 at the beginning ,then it should be true for n = 1 + 1 = 2 as per our later verification that if the formula applies for n = k then , it is also true for n = k + 1. Hence it must be true for n = 2 , 3 , 4 ..etc…that is for all integral values of n .

It is very important to follow both the steps mentioned above in that order , The first step ensures that the given formula is correct by checking at the lowest level of n = 1 or 2 or whatever is relevant.

Then we should check its applicability as per the third step to prove its validity at any integral value of n.

This method has certain limitations by its very nature .

1.It can be applied only for an integral value of “n” the number of terms.

2.We should know the formula or answer ahead , to prove that it is applicable., that is we are not deriving a formula here but proving a given formula.

There are several standard examples for this at the school and college levels and hence we shall confine ourselves with a few important points to remember in adopting this method.

We should adopt a good nomenclature for the problem ,defining clearly all the terms. For example when dealing with problems on summation of series, put

sum to ‘n’ terms as s(n) and ‘n’ th. term as t(n) and note that

s(n) = t(1) +t(2) +……..t(n-1) +t(n) and

s(n+1)=s(n) + t(n+1).

After initial verification for n=1,use the given formula to be proved for s(n) in

s(n+1)=s(n)+t(n+1)

As we have assumed that the given formula is true for ‘n’. Substitute (n+1) for n in L.H.S. to get at what we have to obtain from R.H.S. Now take L.H.S. and substituting for t(n+1) try to maneuver the right hand side to make it equal to left hand side .

In dealing with problems to prove divisibility , proceed similarly and try to convert the R.H.S. in to multiples of the required divisor by splitting / combining them , using the assumed fact for a value of ‘n’ and other general known factors.

Here , now we shall include an example from determinants asked by a reader, which uses this concept in a different context and is quite illustrative of the power of this method.

PROBLEM:

To show that determinant of A = determinant of its transpose

TERMINOLOGY:
let |A| be determinant of order n.
let its transpose be |T|
let elements of |A| be represented by aij...that is the |A|=
a11,a12......a1n
a21,a22......a2n
.........................
an1,an2......ann
similarly let elements of transpose |T| be tij…that is |T|=
t11,t12……..t1n		since |T| is transpose		|T|=	a11,a21,……….an1
t21,t22……..t2n		of |A|,we have tij=aji			a12,a22,………..an2
…………………..					……………………….
tn1,tn2……..tnn					a1n,a2n,…………ann
let cofactor of element aij be |Pij|...and cofactor of element tij be |Qij|
hence expanding |A| by elements of its column no.1
|A| = sigma [ai1*|Pi1|]...from i=1 to n......................................1
similarly expanding |T| by elements of its row.no.1
|T| = sigma[t1i*|Q1i] from i=1 to n................................................2
INDUCTION:
1.let us test it for n=2
|A| = a11,a12
a21,a22
=A11*A22 - A12*A21
|T|= a11,a21
a12,a22
=a11*a22-a12*a21 = |A|
hence the theorem is correct for n=2
2.let us assume that the theorem is true for n th order determinant
that is |A| = |T| for order of n
3.let us prove that then it is true for n+1
expanding |A| and |T| of order n+1 by the elements in their first column and first row respectively,we get
|A| = sigma[ai1*|Pi1|] where |Pi1| is as we know a determinant of order n.
=sigma[t1i*|Pi1|].............since…. ai1=t1i
=sigma[t1i*|Q1i].............since for determinants of order n ,it is already assumed under 2, that the theorem is valid,hence |Pi1|=|its transpose|=|Q1i|
|A|=sigma[t1i*|Q1i|]=|T|