Prove the Following using Principle of Mathematical induction
- Prove that for any positive integer number n , n 3 + 2 n is divisible by 3
- Prove that
1 3 + 2 3 + 3 3 + ... + n 3 = n 2 (n + 1) 2 / 4
for all positive integers n.
- For every n ∈ N, 2n3 + 3n2 + n is divisible by 6.
- Prove by induction that
1 · 2 + 2 · 3 + 3 · 4 + · · · n · (n + 1) = n(n + 1)(n + 2)/ 3
- For every n ≥ 2 , n3-n is multiple of 6
- For every n ≥ 7, 3n ≥ n!
- For all n ≥ 1
(1+x)n ≥ 1+nx
Where (1+x) > 0
- If n ∈ N, then 1·3+2·4+3·5+4·6+··· + n(n+2) = n(n+1)(2n+7) /6
- Prove that 3 +32 +3 3 +34 +··· +3n = (3n+1 −3)/ 2 for every n ∈ N.
- Prove that 1/ 1 + 1/ 4 + 1/ 9 +··· + 1/ n2 ≤ 2− 1/ n
- For all n > 1, 8n – 3n is divisible by 5.
Solution to Problem 1:
Let Statement P (n) is defined by
n
3 + 2 n is divisible by 3
Step 1:
Basic Step
We first show that p (1) is true. Let n = 1 and calculate n
3 + 2n
1
3 + 2(1) = 3
3 is divisible by 3
hence p (1) is true.
STEP 2:
Inductive Hypothesis
We now assume that p (k) is true
k
3 + 2 k is divisible by 3
is equivalent to
k
3 + 2 k = 3 B , where B is a positive integer.
Step 3:
Inductive Steps
We now consider the algebraic expression (k + 1)
3 + 2 (k + 1); expand it and group like terms
(k + 1)
3 + 2 (k + 1) = k
3 + 3 k
2 + 5 k + 3
= [ k
3 + 2 k] + [3 k
2 + 3 k + 3]
= 3 B+ 3 [ k
2 + k + 1 ] = 3 [ B + k
2 + k + 1 ]
Hence (k + 1)
3 + 2 (k + 1) is also divisible by 3 and therefore statement P(k + 1) is true.
Solution to Problem 2:
Statement P (n) is defined by
1
3 + 2
3 + 3
3 + ... + n
3 = n
2 (n + 1)
2 / 4
Step 1:
Basic Step
We first show that p (1) is true.
Left Side = 1
3 = 1
Right Side = 1
2 (1 + 1)
2 / 4 = 1
hence p (1) is true.
STEP 2:
Inductive Hypothesis
We now assume that p (k) is true
1
3 + 2
3 + 3
3 + ... + k
3 = k
2 (k + 1)
2 / 4
Step 3:
Inductive Steps
add (k + 1)
3 to both sides
1
3 + 2
3 + 3
3 + ... + k
3 + (k + 1)
3 = k
2 (k + 1)
2 / 4 + (k + 1)
3
factor (k + 1)
2 on the right side
= (k + 1)
2 [ k
2 / 4 + (k + 1) ]
set to common denominator and group
= (k + 1)
2 [ k
2 + 4 k + 4 ] / 4
= (k + 1)
2 [ (k + 2)
2 ] / 4
We have started from the statement P(k) and have shown that
1
3 + 2
3 + 3
3 + ... + k
3 + (k + 1)
3 = (k + 1)
2 [ (k + 2)
2 ] / 4
Which is the statement P(k + 1).
Solution to Problem 3:
Let P(n)
2n
3 + 3n
2 + n is divisible by 6
Step 1:
Basic Step
P(1) is just that 2 + 3 + 1 is divisible by 6, which is trivial.
STEP 2:
Inductive Hypothesis
We now assume that P (k) is true
Ie.
2k
3 + 3k
2 + k is divisible by 6
Step 3:
Inductive Steps
We have to prove P(k+1)
Now
2(k + 1)
3 + 3(k + 1)
2 + (k + 1)
= 2(k
3 + 3k
2 + 3k + 1) + 3(k
2 + 2k + 1) + (k + 1)
= (2k
3 + 3k
2 + k) + (6k
2+ 6k + 2 + 6k + 3 + 1)
= (2k
3 + 3k
2 + k) + 6(k
2 + 2k + 1)
The first term is divisible by 6 since P(k) is true and the second term is a multiple of 6. Hence, the last quantity is divisible by 6
Solution to Problem 4:
Statement P (n) is defined by
1 · 2 + 2 · 3 + 3 · 4 + · · · n · (n + 1) = n(n + 1)(n + 2)/ 3
Step 1:
Basic Step
We first show that p (1) is true.
Left Side = 1.2 = 2
Right Side = 1 (1 + 1)(1+2) / 3 = 2
hence p (1) is true.
STEP 2:
Inductive Hypothesis
We now assume that p (k) is true
1 · 2 + 2 · 3 + 3 · 4 + · · · k · (k + 1) = k(k + 1)(k + 2)/ 3
Step 3:
Inductive Steps
We have to prove P(k+1)
Now
1 · 2 + 2 · 3 + 3 · 4 + · · · (k +1)· [(k+1) + 1) = (k+1)[(k +1)+ 1][(k+1) + 2]/ 3
Taking LHS
1 · 2 + 2 · 3 + 3 · 4 + · · · (k +1)· [(k+1) + 1)
=1 · 2 + 2 · 3 + 3 · 4 + · ·k(k+1) + (k +1)· [(k+1) + 1)
= k(k + 1)(k + 2)/ 3 + (k +1)· [(k+1) + 1)
= k(k + 1)(k + 2)/ 3 + (k +1)· (k+2)
=(k+1)(k+2) [ k/3 +1]
=(k+1)(k+2)(k+3)/3
Which is the statement P(k + 1).
Solution to Problem 6:
Let Statement P (n) is defined by
for all
n > 7, n! > 3
n
Step 1:
Basic Step
Let
n = 7
n! > 3n
7!= 5040
37= 2187
So p(7) is true
STEP 2: Inductive Hypothesis
We now assume that p (k) is true
That is, k! > 3k
Step 3: Inductive Steps
Let n = k + 1.
Then:
(k+1)! =(k+1)k!
>(k+1) 3k
Now k > 7
So (k+1) >3
>3. 3k
>3k+1
Then P(n) holds for n = k + 1, and thus for all n > 7
Solution to Problem 7:
Let Statement P (n) is defined by
(1+x)n ≥ 1+nx
Where (1+x) > 0
Step 1: Basic Step
Let n = 1
(1+x)n ≥ 1+nx
(1+x) ≥ 1+x
Which is true
So p(1) is true
STEP 2: Inductive Hypothesis
We now assume that p (k) is true
(1+x)k ≥ 1+kx
Step 3: Inductive Steps
Let n = k + 1.
Then:
(1+x)k+1 ≥ 1+(k+1)x
Taking the LHS
(1+x)k+1 =(1+x)(1+x)k
Now from hypothesis we know that
(1+x)k ≥ 1+kx
Also (1+x) > 0
So (1+x)k+1 ≥(1+x)( 1+kx)
≥[1+kx2+ (k+1)x]
Now kx2 is a positive quantity so we can say that
≥[1+ (k+1)x]
Which is P(k+1)
Solution to Problem 11:
Let Statement P (n) is defined by
for all n > 1, 8n – 3n is divisible by 5.
Step 1: Basic Step
Let n = 1.
Then the expression 8n – 3n evaluates to 81 – 31 = 8 – 3 = 5, which is clearly divisible by 5.
STEP 2: Inductive Hypothesis
We now assume that p (k) is true
That is, that 8k – 3k is divisible by 5.
Step 3: Inductive Steps
Let n = k + 1.
Then:
8k+1 – 3k+1 = 8k+1 – 3×8k + 3×8k – 3k+1
= 8k(8 – 3) + 3(8k – 3k) = 8k(5) + 3(8k – 3k)
The first term in 8k(5) + 3(8k – 3k) has 5 as a factor (explicitly), and the second term is divisible by 5 (by assumption). Since we can factor a 5 out of both terms, then the entire expression, 8k(5) + 3(8k – 3k) = 8k+1 – 3k+1, must be divisible by 5.
Then P(n) holds for n = k + 1, and thus for all n > 1.
Related Topics
link to this page by copying the following text
Go back to Class 11 Main Page using below links
Class 11 Maths
Class 11 Physics
Class 11 Chemistry
Class 11 Biology