Inductive Proof

Inductive Proof

AU: May-07,08,12,14,16,17, Dec.-12, Marks 16

Inductive proofs are special proofs based on some observations. It is used to prove recursively defined objects. This type of proof is also called as proof by mathematical induction.

The proof by mathematical induction can be carried out using following steps

1. Basis: In this step we assume the lowest possible value. This is an initial step in the proof of mathematical induction.

For example, we can prove that the result is true for n = 0 or n = 1.

2. Induction hypothesis: In this step we assign value of n to some other value k. That mean we will check whether the result is true for n = k or not.

3. Inductive step: In this step, if n = k is true then we check whether the result is true for n = k + 1 or not. If we get the same result at n = k + 1 then we can state that given proof is true by principle of mathematical induction.

Example 1.4.1 Prove by induction on n that Σⁿ_i=0 i = n(n+1)/2

AU: May-12, Marks 6

Solution: Initially,

1) Basis of induction -

Assume, n = 1. Then,

L.H.S= n, = 1

R.H.S = n(n+1)/2 = 1(1+1)/2 = 2/2 = 1

Now,

2) Induction hypothesis -

Now we will assume n = k and will obtain the result for it. The equation then becomes,

1+2+3+ ... + k = (k(k+1)/2

3) Inductive step -

Now we assume that equation is true for n = k. And we will then check if it is also true for n = k + 1 or not.

Consider the equation assuming n = k + 1

L.H.S. = 1+ 2+ 3... + k + k + 1             equation (1)

k(k+1)/2 +k+1

= k(k + 1) + 2(k + 1)/2

= (k+ 1) (k + 2)/2                              taking common factor

i.e. = (k + 1) (k + 1 + 1)/2

= R.H.S.

Example 1.4.2 Prove: n!>= 2^n-1

Solution: Consider,

1. Basis of induction - Let n = 1 then L.H.S. = 1 R.H.S. = 2^{1 - 1} =2⁰ =1 hence n!>= 2^n-1 is proved.

2. Induction hypothesis - Let n = n + 1 then

k! = 2^k-1 where k > = 1

then (k + 1)! = (k + 1)k! by definition of n!

= (k+1) 2^{k -1} = 2 × 2^k-1 = 2^k

Example 1.4.3 Prove that 1² + 2² + 3² + ... + n² = Σⁿ_i=1 i² = n(n + 1) (2n + 1)/6 using mathematical induction. AU: May-07, 16, Marks 6, May-14, Marks 8

Solution: We will first prove it by basis of induction and then will consider induction hypothesis.

1. Basis of induction -

Let n = 1

L.H.S. = 1² = 1

R.H.S. = 1(1+1)(2.1+1) /6 = 6/6

R.H.S. = 1

As L.H.S. = R.H.S it is proved for n = 1.

2. Induction hypothesis - Let, n = k.

Then

1² + 2² + …….. + k² = Σ^k_i=1 i² = k(k+1)(2k+1) /6 is true

Now, we will try to prove it for n = k + 1. Hence we will substitute n by k + 1.

1² + 2² + 3² +............+ (k+1)² = Σ^k+1_i=1 i² = (k+1)(k+1+1)(2(k+1)+1) /6

L.H.S. = 1² + 2² + 3² +...... + k² + (k+1)²

We will substitute equation (1) and we will get,

= (k+1) [k(2k+1)+6k+6 /6] = (k+1) [2k²+k+6k+6 /6]

= (k+1) [2k² +7k+6 /6] = (k+1)(2k²+4k+3k+6) /6

= (k+1)(2k(k+2)+3(k+2)) /6 = (k+1)((2k+3)(k+2)) /6

= (k+1)((k+2)(2k+3)) /6 = = (k+1)(k+1+1)(2(k+1)+1) /6

= R.H.S.

As L.H.S. = R.H.S., it is true that using n = k + 1 the given expression can be proved.

Example 1.4.4 Prove 1+4+ 7+.......+ (3n-2) = n(3n-1)/2 for n > 0

Solution: Consider,

1. Basis of induction -

Let, n = 1,

L.H.S. (3.1-2) = 1

R.H.S. = 1(3.1-1) /2 = 2/2 = 1

As L.H.S. = R.H.S. given expression is true for n = 1.

2. Induction hypothesis - We assume that the given expression is true for n = k.

i.e.

1+4+7+.......+(3k-2) = k(3k-1) is true.                …...(1)

Now we will prove it for n = k + 1.

L.H.S. 1+4 +7 +...... + (3k-2)+(3(k+1)-2)

We will substitute R.H.S. of equation (1).

 = k(3k-1) /2 +(3(k+1)-2) = k(3k-1)+2[3(k+1)-2] /2

= 3k²-k+6k+2 /2 = 3k²+5k+2 /2

= 3k²+2k+3k+2 /2 = (2k+2)+(3k² +3k) /2

= 2(k+1)+3k(k+1) /2 = (k+1)(3k+2) /2 = (k+1)(3(k+1)-1) /2

= R.H.S.

As L.H.S. = R.H.S. the given expression is true for n = k + 1.

Example 1.4.5 Prove: 2ⁿ > n³ where n ≥ 10.

Solution: 1) Basis of induction -

Initially we assume,

n = 10 then

2¹⁰ > (10)³ is true

2) Induction hypothesis -

Now assume, n = k then

2^K > k³

3) Inductive step-

Now we will assume k = k + 1 then the equation becomes

L.H.S. = 2^(k+1)

= 2.2^k

≥ (1 + 1/10)³.2^k

≥ (1 + 1/k)³. 2^k

But as 2^k > k³ we will replace 2^k by k³ then

≥ (1+ 1/k)³. k³

≥ (k+1 /k)³. k³

≥ (k+1)³ /k³. k³

≥ (k+1)³

= R.H.S.

Hence 2^{k + 1} ≥ (k + 1)³ is also true.

This proves 2ⁿ > n³ for n ≥ 10.

Example 1.4.6 Prove: 2ⁿ > n using principle of mathematical induction.

Solution:

1) Basis of induction - Assume n = 1 then,

2ⁿ > n becomes

2¹ > 1

2 > 1

This also implies 2ⁿ - n > 0

2) Induction hypothesis - Assume n = k is true

i.e. 2^k > k

i.e. 2^k - k > 0

Thus 2^k - k implies a positive number. i.e.

2^k - k = t

3) Inductive step - Assume k = k + 1 then

2^k+1 - (k + 1)

2^k.2 - (k+1)

But from equation (1) 2^k = k + t then

(k+t).2 - k - 1

i.e. 2k + 2t - k - 1

k + 2t - 1

> 0 i.e. as positive number.

This implies 2^k+1 > k + 1. Hence 2ⁿ > n true.

Example 1.4.7 Prove 2ⁿ <= n! for all n >= 4.

Solution:

1. Basis of induction - Let n = 4 then

L.H.S. 2⁴ = 16

R.H.S.= n! (4)! (1 x 2 x 3 x 4) = 24

i.e. L.H.S <= R.H.S.

Hence 2 <= n! is proved.

2. Induction hypothesis

We assume n = k and

2^k <= k! is also true where k >= 4.

Now we have to consider n = k + 1, then

L.H.S. = 2^k+1 = 2^k. 2¹

R.H.S. = (k + 1)!= (k + 1) k!

By induction hypothesis we have

k! > 2^k

(k + 1) k! > 2^k.2¹ where k >= 4

i.e.

2^k+1 <= (k+1)! is true.

As it is true for n = k + 1, the given expression is proved.

Example 1.4.8 Prove that for every integer n≥0 the number 4²ⁿ⁺¹ + 3ⁿ⁺² is multiple of 13.

AU: May-08, 14, Marks 10

Solution: We will prove this using method of induction.

Basis - Assume

n = 1

P(1) = 4²⁽¹⁾⁺¹+3¹⁺²

= 4³ + 3³

= 91 which is = 13×7

Hence 4²ⁿ⁺¹ + 3ⁿ⁺² is multiple of 13 when n = 1.

Inductive step - Assume n = k

P(k) = 4^2k+1 + 3^k+2

P(k) = 13 m

where m is some integer.

Thus we assume that given expression is true for P(k). Now we will prove that is also true for P(k+1).

Let, n = k +1 then

P(k+1) = 4^2(k+1)+1 + 3^(k+1)+2

We can simplify it as -

= 4^(2k+1)+2 + 3^(k+2)+1

= 4². 4^2k+1+4². (3^k+2 - 3^k+2) + 3¹.3^k+2

equal to zero

Taking common factors as 4² and 3^k+2 we get

= 4² (4^2k+1 + 3^k+2) + 3^k+2 (-4²+3)

= 4² (13m) + 3^k+2(-13).

equation (1)

P(k + 1) = 13 (4²m - 3^k+2)

That is multiple of 13, for P(k + 1).

This proves that given integer is multiple of 13.

Example 1.4.9 Prove for every n ≥ 1 by mathematical induction Σⁿ i³ = {n(n+1)/2}². 

AU: May-17, Marks 16

Solution:

• Base Case

Assume

n = 1 then

L.H.S. = (1)³ = 1

R.H.S. = [1(1+1) /2]² = (2/2)² = 1

As L.H.S. = R.H.S.

Thus the given expression is true for n = 1.

• Inductive Hypothesis

Assume n = k is true

Then 1³+2³+3³ +...+ k³ = [k(k+1) /2]² is also true, for some k in the set of positive integers.

1³+2³+3³ +...+k³ = [k(k+1) /2]² …..(1)

• Inductive Step

We will show that if n = k is true then it implies n = k + 1 is also true.

L.H.S. = 1³+2³+3³+ ... + k³+(k+1)³

R.H.S. = [(k+1)(k+2) /2]²

From equation (1)

[k(k+1)³ /2]² +(k+1)³ = k²(k+1)² /4 +(k+1)³

= k²(k+1)² +4(k+1)³ /4

= k²(k²+2k+1)+4(k³ +3k²+3k+1)

= k²(k² +2k+1)+4k³+12k² +12k+4 /4

= k⁴+2k³+k² +4k³ +12k² +12k+4

L.H.S. = k⁴+6k³ +13k² +12k+4 /4   …..(2)

Now consider R.H.S.

R.H.S. = [(k+1)(k+2) /2]²

= (k+1)² (k+2)² /4

= (k² +2k+1)(k² +4k+4) /4

= k⁴+4k³ +4k² + 2k³ +8k² +8k+k² +4k+4 /4

R.H.S. = k⁴ +6k³ +13k² +12k+4 /4    …..(3)

From equation (2) and equation (3) we get

L.H.S. = R.H.S. is proved for n = k +1

Thus given expression is true.

Review Question

1. Explain the different forms of proof with examples. AU: Dec.-12, Marks 8