MATHEMATICAL INDUCTION:

**Mathematical induction is a unique and special way to prove the things, in only two steps.**

*Step 1.*Show that it is true for n = 1.

*Step 2.*Show that if n = k is true then n = k+1 is also true.

For example:

Prob. By principal of mathematical induction prove that

11n+2 + 122n+1 is divisible by 133, n ∈ N.

Solution.

*Step 1 P(1)-*Show it is true for n = 1

Yes 3059 is divisible by 133.

111+2 + 122(1)+1 is true.

*Step 2 P(k)-*Assume it is true for n = k

11k+2 + 122(k)+1 is true.

(above line is an assumption only, which we will use as a fact in rest of the solution)

Now, prove that 11(k+1)+2 + 122(k+1)+1 is divisible by 133. (here n = k +1 now, P(k+1))

**We have,**

P(k+1)

11(k+1)+2 + 122(k+1)+1 = 11k+3 + 122k+3

11(k+1)+2 + 122(k+1)+1 = 11k+2 x 11 + 122k+1x 122

11(k+1)+2 + 122(k+1)+1 = (11k+2 x 11) + (122k+1x 144 )

11(k+1)+2 + 122(k+1)+1 = (11k+2 x 11) + (122k+1x (11 + 133))

11(k+1)+2 + 122(k+1)+1 = (11k+2+ 122k+1)x 11+(122n+1 x 133)

11(k+1)+2 + 122(k+1)+1 = ((11k+2+122k+1)x 11)+(122n+1 x 133)

Here 11k+2+122k+1 is divisible by 133 as assumed in n = k, P(1),

And 122n+1 x 133 is multiple of 133 so it is divisible by 133.

So,

11(k+1)+2 + 122(k+1)+1 = ((divisible by 133)x 11)+(divisible by 133)

11(k+1)+2 + 122(k+1)+1 = divisible by 133.

In this problem

If n = n, i.e, P(1) is true then n = n+1, i.e, P(n+1) is also true. Hence proved.

Problems based on above study:

Prob. Prove the following proposition

12 + 22 + 32 +...........+ n2 = (n (n+1)(2n+1) ) /6.

Prob. By principal of mathematical induction prove that

11n+2 + 122n+! is divisible by 133, n ∈ N.

Prob. By mathematical induction prove that for any integer n, 11n+2 + 122n+1 is divisible by 133.

Prob. Show that 2 + 4 + 6 + …… + 2n = n (n+1) by mathematical induction.

Prob. Prove by induction that the sum of the cubes of three consecutive integers is divisible by 9.

Prob. Prove by mathematical induction that n2 + n is an even number for all natural numbers, n ≥ 1.

Prob. Prove by using method of induction-

12 + 22 + 32 +.......+ (3n - 2)2 = (n(6n2 - 3n -1)) /2.

Prob. Prove by mathematical induction -

12 - 22 + 32 -............+ (-1)n+1n2 = ((-1)n+1n(n+1)) /2.

**Discrete Structure**

**EasyExamNotes.com covered following topics in these notes.**

- SET
- Mathematical Induction
- Relation
- Binary operations
- Algebraic struture
- Group
- Numerical problems on GROUP
- Subgroup
- Abelian Group or Commutative group
- Coset
- Factor or Quotient group
- Cyclic group
- Ring
- Numerical problems on RING
- Field
- POSET, Hasse diagram,Upper and Lower Bounds
- Hasse diagram
- Upper and Lower Bounds
- Lattice
- Recurrence relation numerical problems
- How to solve generating function

**A list of Video lectures**

## Post a Comment

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.