In the previous section, we saw the basics of mathematical induction. We saw some examples also. In this section we will see problems involving inequality.
Let us see an example. It can be written in 4 steps:
1.
Consider any positive integer n. A mathematician
tells us that, this n will be always less than twice it's value.
That is: n < 2n
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 1
• Put n = 1 in the RHS. We get: RHS = 2 × 1 = 2
• LHS < RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 5 steps:
(i) Put n = k in the LHS. We get: LHS = k
• Put n = k in the RHS. We get: 2 × k = 2k
• We assume that, this LHS is less than RHS. That is., k < 2k
(ii) Put n = (k+1) in the LHS. We get: LHS = k+1
• Put n = (k+1) in the RHS. We get: RHS = 2(k+1) = 2k+2
(iii) We have to prove that LHS in (ii) is less than RHS in (ii)
• That is., we have to prove that: k+1 < 2k+2
♦ For proving this, we can use the statement in (i)
♦ Remember that, we assume the statement in (i) to be true.
(iv) Consider the statement in (i): k < 2k
• Adding '1' on both sides, we get: k+1 < 2k+1
• So k+1 will be obviously less than 2k+2
• Thus the statement in (iii) is proved.
• So we proved that:
If the statement is true for n = k, it will be true for n = (k+1)
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n = (k+1)
• Since both are proved, we can write:
The given statement is true.
Let us write the above steps in the condensed form:
Problem:
Prove that for any positive integer n, n < 2n
Solution:
1. For any positive integer n, let P(n) denote the given statement.
Then we can write: P(n): n < 2n
2. Basic step: (n=1)
$\begin{array}{ll}
\phantom{\Rightarrow~}P(1): &
1 & {}<{} & (2 × 1) & {} \\
{\Rightarrow~} P(1): & 1 & {}<{} & 2 & {} \\
\end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
P(k): k < 2k
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll}
\phantom{\Rightarrow~}P(k+1): & k+1 & {}<{} & 2(k+1) & {} \\
{\Rightarrow~} P(k+1): & k+1 & {}<{} & 2k+2~\color
{green}{\text{---- (a)}} & {} \\
{}& {} & {}& \color
{green}{\text{[We want to prove (a)]}} & {} \\
{}&{}& {}&{} & {} \\
\phantom{\Rightarrow~}P(k): & k & {}<{} & 2k~\color
{green}{\text{---- (b)}} & {} \\
{} & k+1 & {}<{} & 2k+1~\color
{green}{\text{---- (c)}} & {} \\
{}&{}& {}& \color
{green}{\text{[Adding '1' on both sides]}} & {} \\
{}&{}& {}&{} & {} \\
{} & 2k+1 & {}<{} & 2k+2~\color
{green}{\text{---- (d)}} & {} \\
{}&{} & {}& \color
{green}{\text{[Since 'k' is a +ve integer]}} & {} \\
{}&{}& {}&{} & {} \\
{} & k+1 & {}<{} & 2k+1 ~~ <~~2k+2 & {} \\
{}&{} & {}& \color
{green}{\text{[Using (c) and (d)]}} & {} \\
{} & k+1 & {}<{} & 2k+2 & {} \\
{}&{} & {}& \color
{green}{\text{[Picking first and third items]}} & {} \\
{}&{} & {}& \color
{green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\
\end{array}$
• So P(k+1) is true.
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of
mathematical induction, P(n) is true for any positive integer n.
5. We can write the conclusion in another way also:
• We want to prove that k+1 < 2k+2
• In (ii), we saw that, k+1 < 2k+1
• Since k is positive integer, 2k+1 will be less than 2k+2
• So we can write: k+1 < 2k+1 < 2k+2
• Picking the first and last expressions, we get: k+1 < 2k+2
Let us see another example. It can be written in 4 steps:
1.
Consider any positive integer n. A mathematician
tells us that, this n will be always less than 2 raised to n.
That is: 2n > n
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 21 × 1 = 2
• Put n = 1 in the RHS. We get: RHS = 1
• LHS > RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 5 steps:
(i) Put n = k in the LHS. We get: LHS = 2k
• Put n = k in the RHS. We get: RHS = k
• We assume that, this LHS is greater than RHS. That is., 2k > k
(ii) Put n = (k+1) in the LHS. We get: LHS = 2k+1
• Put n = (k+1) in the RHS. We get: RHS = k+1
(iii) We have to prove that LHS in (ii) is greater than RHS in (ii)
• That is., we have to prove that: 2k+1 > k+1
♦ For proving this, we can use the statement in (i)
♦ Remember that, we assume the statement in (i) to be true.
(iv) Statement in (i) is: 2k > k
• Adding 1 on both sides, we get: 2k +1 > k+1
(v) Let us replace the '1' on the left side by 2k. We get:
2k + 2k > k+1
• This is true because, k is a +ve integer. 2k will be greater than 1.
(vi) The left side can be simplified. We get: 2 × 2k > k+1
• This is same as: 2k+1 > k+1
• So the statement in (iii) is true.
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n = (k+1)
• Since both are proved, we can write:
The given statement is true.
Let us write the above steps in the condensed form:
Problem:
Prove that for any positive integer n, 2n > n
Solution:
1. For any positive integer n, let P(n) denote the given statement.
Then we can write: P(n): 2n > n
2. Basic step: (n=1)
$\begin{array}{ll}
\phantom{\Rightarrow~}P(1): &
2^1 & {}>{} & 1 & {} \\
{\Rightarrow~} P(1): & 2 & {}>{} & 1 & {} \\
\end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
P(k): 2k > k
• Assume that, the above statement is true.
(ii) n = k+1
$\begin{array}{ll}
P(k+1): & 2^{k+1} & {}>{} & k+1~\color
{green}{\text{---- (a)}} & {} \\
{}& {} & {}& \color
{green}{\text{[We want to prove (a)]}} & {} \\
{}&{}& {}&{} & {} \\
P(k): & 2^k & {}>{} & k~\color
{green}{\text{---- (b)}} & {} \\
{} & 2^k+1 & {}>{} & k+1~\color
{green}{\text{---- (c)}} & {} \\
{}&{}& {}& \color
{green}{\text{[Adding '1' on both sides]}} & {} \\
{}&{}& {}&{} & {} \\
{} & 2^k & {}>{} & 1~\color
{green}{\text{---- (d)}} & {} \\
{}&{} & {}& \color
{green}{\text{[Since 'k' is a +ve integer]}} & {} \\
{} & 2^k+2^k & {}>{} & k+1~\color
{green}{\text{---- (e)}} & {} \\
{}&{} & {}& \color
{green}{\text{[Using (c) and (d)]}} & {} \\
\Rightarrow & 2 × 2^k & {}>{} & k+1 & {} \\
\Rightarrow & 2^{k+1} & {}>{} & k+1 & {} \\
{} &{} & {}& \color
{green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\
\end{array}$
• So P(k+1) is true.
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of
mathematical induction, P(n) is true for any positive integer n.
Let us see another problem involving inequality. It can be written in 4 steps:
1.
Consider any positive integer n. A mathematician
tells us that, '4' raised to this n will be always greater than (n+1).
That is: 4n > n+1
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 41 = 4
• Put n = 1 in the RHS. We get: RHS = 1+1 = 2
• LHS > RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 5 steps:
(i) Put n = k in the LHS. We get: LHS = 4k
• Put n = k in the RHS. We get: RHS = k+1
• We assume that, this LHS is greater than RHS. That is., 4k > k+1
(ii) Put n = (k+1) in the LHS. We get: LHS = 4(k+1)
• Put n = (k+1) in the RHS. We get: RHS = (k+1)+1
(iii) We have to prove that LHS in (ii) is greater than RHS in (ii)
• That is., we have to prove that: 4(k+1) > (k+1)+1
♦ For proving this, we can use the statement in (i)
♦ Remember that, we assume the statement in (i) to be true.
(iv) In (i), it is said that, 4k is greater than (k+1)
• So (4k +1) will be greater than [(k+1)+1]
• So (4k + 4k) will be greater than [(k+1)+1] (since k is a positive number, 4k will be greater than 1)
⇒ (2 × 4k) will be greater than [(k+1)+1]
• So (4k × 4k) will be greater than [(k+1)+1] (since k is a positive number, 4k will be greater than 2)
⇒ 4(k+1) will be greater than [(k+1)+1]
Thus we proved that: 4(k+1) > (k+1)+1
• That is:
If the statement is true for n = k, it will be true for n = (k+1)
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n = (k+1)
• Since both are proved, we can write:
The given statement is true.
Let us write the above steps in the condensed form:
Problem:
Prove that for any positive integer n, 4n > n+1
Solution:
1. For any positive integer n, let P(n) denote the given statement.
Then we can write: P(n): 4n > n+1
2. Basic step: (n=1)
$\begin{array}{ll}
\phantom{\Rightarrow~}P(1): &
4^1 & {}>{} & 1+1 & {} \\
{\Rightarrow~} P(1): & 4 & {}>{} & 2 & {} \\
\end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
P(k): 4k > k+1
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll}
P(k+1): & 4^{k+1} & {}>{} & k+1+1~\color
{green}{\text{---- (a)}} & {} \\
{}& {} & {}& \color
{green}{\text{[We want to prove (a)]}} & {} \\
{}&{}& {}&{} & {} \\
P(k): & 4^k & {}>{} & k+1~\color
{green}{\text{---- (b)}} & {} \\
{} & 4^k+1 & {}>{} & k+1+1~\color
{green}{\text{---- (c)}} & {} \\
{}&{}& {}& \color
{green}{\text{[Adding '1' on both sides]}} & {} \\
{}&{}& {}&{} & {} \\
{} & 4^k & {}>{} & 1~\color
{green}{\text{---- (d)}} & {} \\
{}&{} & {}& \color
{green}{\text{[Since 'k' is a +ve integer]}} & {} \\
{} & 4^k+4^k & {}>{} & k+1+1~\color
{green}{\text{---- (e)}} & {} \\
{}&{} & {}& \color
{green}{\text{[Using (c) and (d)]}} & {} \\
\Rightarrow & 2 × 4^k & {}>{} & k+1+1~\color
{green}{\text{---- (f)}} & {} \\
{}&{}& {}&{} & {} \\
{} & 4 & {}>{} & 2~\color
{green}{\text{---- (g)}} & {} \\
{} & 4 × 4^k & {}>{} & k+1+1 & {} \\
{}&{} & {}& \color
{green}{\text{[Using (f) and (g)]}} & {} \\
\Rightarrow & 4^{k+1} & {}>{} & k+1+1 & {} \\
{} &{} & {}& \color
{green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\
\end{array}$
• So P(k+1) is true.
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of
mathematical induction, P(n) is true for any positive integer n.
Let us see another problem involving inequality. We will directly write the solution in the condensed form.
Problem:
Prove that for positive integer n, 2n+1 < 2n, n ≥ 3
Solution:
1. For positive integer n ≥ 3, let P(n) denote the given statement.
Then we can write: P(n): 2n+1 < 2n, n ≥ 3
2. Basic step: (n=3)
$\begin{array}{ll}
P(3): & [(2 × 3)+1] & {}<{} & 2^3 & {} \\
{} & [6+1] & {}<{} & 8 & {} \\
{} & 7 & {}<{} & 8 & {} \\
\end{array}$
• So P(n) is true for n=3
3. Inductive step: (n=k) and (n= k+1)
(i) n= k [positive integer k ≥ 3]
P(k): 2k+1 < 2k
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll}
P(k+1): & 2(k+1)+1 & {}<{} & 2^{k+1} & {} \\
{} & 2k+2+1 & {}<{} & 2^{k+1}~\color
{green}{\text{---- (a)}} & {} \\
{}& {} & {}& \color
{green}{\text{[We want to prove (a)]}} & {} \\
{}&{}& {}&{} & {} \\
P(k): & 2k+1 & {}<{} & 2^k~\color
{green}{\text{---- (b)}} & {} \\
{} & 2k+2+1 & {}<{} & 2^k+2~\color
{green}{\text{---- (c)}} & {} \\
{}&{}& {}& \color
{green}{\text{[Adding '2' on both sides]}} & {} \\
{}&{}& {}&{} & {} \\
{} & 2^k & {}>{} & 2~\color
{green}{\text{---- (d)}} & {} \\
{}&{} & {}& \color
{green}{\text{[Since k ≥ 3]}} & {} \\
{} & 2k+2+1 & {}<{} & 2^k+2^k & {} \\
{}&{} & {}& \color
{green}{\text{[Using (c) and (d)]}} & {} \\
\Rightarrow & 2k+2+1 & {}<{} & 2 × 2^k & {} \\
\Rightarrow & 2k+2+1 & {}<{} & 2^{k+1} & {} \\
{} &{} & {}& \color
{green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\
\end{array}$
• That is., P(k+1) is true.
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of
mathematical induction, P(n) is true for any positive integer n
In the next section, we will see more solved examples.
Copyright©2021 Higher secondary mathematics.blogspot.com
No comments:
Post a Comment