Mathematical Induction | TOC

Mathematical Induction

Suppose P(N) is a statement where N is any integer and we wish to show that P(N) is true for all value of N beginning with some starting value N(o) to do this it is sufficient to show the following condition.  

1. P(No) is true  (i.e) statement is valid for No)

2. For any integer K>=No if P(k) is true than P(k+1) is also true.

Step for Mathematical Induction:

1. Basic Step: In basic step we proof statement is true for No. (i.e P(No) is true)

2. Induction Step: This induction step is divided into three sub steps.

    a. Induction Hypothesis: In this step we assume statement is true for any  

        (k>=No) i.e P(k) is true.

    b. Statement to be proof: In this step we write the statement for P(k+1)

        which is to be proof assuming P(k) is true for (k>=No)

    c. Induction Step: In this step we proof the statement for P(k+1).

Question 1: Let P(N) be the statement

                                2⁰+2¹+ ..... +2^N =2^N+1-1

                 Using mathematical induction show that P(N) is true for every N>=0

Proof: 

1. Basic Step: 

    We have to show statement is true for 0 i.e P(0) is true.

          2⁰ = 2⁰⁺¹ -1 

            1=1

       L.H.S=R.H.S

    Therefor statement is true for N=0

2. Induction Hypothesis:

    For any k>=0 , P(k) is true.

    i.e  2⁰ + 2¹ + 2² + ...... + 2^k = 2^k+1-1

3. Statement to be shown:

    For any k>=0 we have to show that P(k+1) is also true

    i.e  2⁰ + 2¹ + 2² + ...... + 2^k+1 = 2^k+2 -1

    Assuming P(k) is true

4. Induction Step:

    2⁰ + 2¹ + 2² + ...... + 2^k + 2^k+1

    2^k+1-1 + 2^k+1

    2 . 2^k+1 - 1

    2^k+2 - 1  hence proved.

Question 2: Let  L ⊆ ∑^* and L² ⊆ L

    Let P(N) is the statement

    L^N ⊆ L

    using Mathematical Induction show that P(N) is true for every N >=2

Proof:

1. Basic Step: 

    We have to show statement is true for N0=2

    i.e P(2)

    L² ⊆ L which is given

    Therefore P(2) is true.

2. Induction Hypothesis:

    For any k>=2  P(k) is true

    i.e  L^k ⊆ L

3. Statement to be shown:

    For any K>=2 if P(k) is true than we have to show that P(k+1) is also true.

    i.e  L^k ⊆ L

4. Induction Step:

    L^k+1 = L^k . L ⊆ L L = L² ⊆L

    L^k+1 ⊆ L Hence proved

Strong Principle of Mathematical Induction:

Suppose P(N) is a statement involving on integer N we wish to prove that P(N) is true for all value of N. Starting with some initial value N₀ to do this it is sufficient to show the following condition.

1. P(N₀) is true.

2. For any integer k>= N₀ if the statement P(N) is true for every N 

    N₀ <= N <=k  than

    P(k+1) is true

Note: What is strong principle of mathematical induction ? Why it is strong ?

In Mathematical Induction Pk is true for 0<=k<=N. There is no justified value of N. But in Strong Mathematical Induction P(N) is true for N₀<=N<=k. In Strong Mathematical Induction we can find the value after N. 

i.e P(k+1)

Question 1: Let L={aaa, aaaaaaa}

                  Suppose P(N) be the statement

                    a^N ∈ L^*

                ^{using principle of strong Mathematical Induction show that P(N) is true for every}  

                    N≥2

Proof:

1. Basic Step: 

    P(12) is true

    a¹²=(a³)⁴=LLLL=L⁴∈L^*

    a¹² ∈ L^*

    Therefore p¹² is true

2. Induction Hypothesis: 

    For every k ≥ 12 , P(N) is true for all (N) with 12 ≤ N ≤ k

    a^N ∈ L^*

3. Statement to be shown:

    For any k ≥ 12 and P(N) is true for all N with 12 ≤ N ≤ k than P(k+1) is also true.

4. Induction Step:

    Case 1: When k=12

        a¹²⁺¹ = a¹³ = (a³)².a⁷ ∈ L² L= L³ ∈ L^*

        a¹³ ∈ L^*

    Case 2: When k=13

        a¹³⁺¹ = a¹⁴ = (a⁷)² ∈  L L= L² ∈ L^*

        a¹⁴ ∈ L^*

    Case 3: When k≥14 can be represented as  k-2 ≥ 12

        Since according to induction hypothesis 

        P(N) is true with 12 ≤ N ≤ k

        We conclude that 

        a^k-2 ∈ L^*

            ^{Since k-2 ≥  12}

                    ^{N ≥ 12}

                    ^P(N)

                    a^N ∈ L^*

        a^k+1 = a^k-2. a³ ∈ L^* L^* = L^*

        a^k+1 ∈ L^*  Hence Proved