Mathematical Induction: Principles, Proof of Series, Divisibility, Equations and Example Problems

Mathematical Induction: Principles, Proof of Series, Divisibility, Equations and Example Problems – What is Mathematical Induction? At this opportunity About the knowledge.co.id will discuss about Kasti Ball and the things that surround it. Let's look at the discussion in the article below to understand it better.

Mathematical Induction: Principles, Proof of Series, Divisibility, Equations and Example Problems

---

Mathematical induction is a method of deductive proof that is used to prove mathematical statements related to a set of numbers that are ordered in an orderly manner.

These numbers are for example natural numbers or non-empty subsets of numbers original. Mathematical induction is only used to check or prove the truth of a statement or formula. And mathematical induction is not for deriving formulas. Mathematical induction cannot be used to derive or find formulas.

The following are some examples of mathematical statements that can be proven true by mathematical induction:

P(n): 2 + 4 + 6 + … + 2n = n (n + 1), n ​​is a natural number

P(n): 6ⁿ + 4 is divisible by 5, for n natural numbers.
P(n): 4n < 2ⁿ, for each natural number n ≥ 4

1. P(m) is true, which means that for n = m, then P(n) is true
2. For each natural number k ≥ m, if P(k) is true then P(k + 1) is also true.

To show that P(1) is true, it suffices to substitute n = 1 for P(n).

If P(n) is presented in equation form, it means that the left-hand side must equal the right-hand side at n = 1, and then we conclude that P(1) is true.

We can apply the same method to show that P(m) is true.

Returning to the domino case above, in order for domino (k + 1) to fall, the earliest domino k must fall.

And then followed by the implication "if domino k falls, then domino (k + 1) falls" can occur.

So, to show the implication "if P(k) is true then P(k + 1) is true", then our first step must be to assume that P(k) is true.

Then looking at these assumptions we show that P(k + 1) is also true.

This process of assuming P(k) is true is called the induction hypothesis.

To show that P(k + 1) is true, we can start from the hypothesis. That is, from the assumption that P(k) is true or from the conclusion, that is, from P(k + 1) itself.

The proof of mathematical induction can be done in the following order:

• Initial step: Show P(1) is true.
• Induction step: Assume that P(k) is true for any k natural numbers, then show that P(k+ 1) is also true based on that assumption.
• Conclusion: P(n) is true for every natural number n.

---

Proof of Series

Before entering into the proof of the series, there are several things that need to be considered carefully regarding the series. Among others:

If

P(n): u₁ +u₂ +u₃ + … + u_n = S_n, so
P(1): u₁ = S₁
P(k): u₁ +u₂ +u₃ + … + u_k = S_k
P(k + 1): u₁ +u₂ +u₃ + … + u_k +u_k+1 = S_k+1

• Example 1:

Prove that 2 + 4 + 6 + … + 2n = n (n + 1), for each of n natural numbers.

Answer:
P(n): 2 + 4 + 6 + … + 2n = n (n + 1)

It will be proved that P(n) is true for each n ∈ N

Initial step:

Shows P(1) is true
2 = 1(1 + 1)

So it is obtained, P(1) is true

Induction step:

Let P(k) be true, namely:
2 + 4 + 6 + … + 2k = k (k + 1), k ∈ N

Will show that P(k + 1) is also true, that is:
2 + 4 + 6 + … + 2k + 2(k + 1) = (k + 1)(k + 1 + 1)

From the assumptions above then:
2 + 4 + 6 + … + 2k = k (k + 1)

Add both sides with u_k+1 :
2 + 4 + 6 + … + 2k + 2(k + 1) = k (k + 1) + 2(k + 1)
2 + 4 + 6 + … + 2k + 2(k + 1) = (k + 1)(k + 2)
2 + 4 + 6 + … + 2k + 2(k + 1) = (k + 1)(k + 1 + 1)

So, P(k + 1) is true

Based on the principle of mathematical induction, it is proven that P(n) is true for each n natural numbers.

• Example 2:

Prove it 1 + 3 + 5 + … + (2n − 1) = n² that's right, for each n natural number.

Answer:
P(n): 1 + 3 + 5 + … + (2n − 1) = n²

Then it will show that P(n) is true for each n ∈ N

• Initial step:
  Will show P(1) is true
  1 = 1²

So, P(1) is true

• Induction step:
  Imagine that P(k) is true, namely:
  1 + 3 + 5 + … + (2k − 1) = k², k ∈ N

This will show that P(k + 1) is also true, namely:
1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = (k + 1)²

From the assumptions above then:
1 + 3 + 5 + … + (2k − 1) = k²

Add both sides with u_k+1 :
1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = k² + (2(k + 1) − 1)
1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = k² +2k+1
1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = (k + 1)²

So, P(k + 1) is also true

Based on the principle of mathematical induction, it is proven that P(n) is true for each n natural numbers.

---

Proof of Division

The statement "a is divisible by b" is synonymous with:

• a multiple b
• b factor of a
• b divide a

If p is divisible by a and q is divisible by a, then (p + q) will also be divisible by a.

For example, 4 is divisible by 2 and 6 is divisible by 2, then (4 + 6) will also be divisible by 2

• Example 1:

Prove 6ⁿ + 4 is divisible by 5, for each n natural number.

Answer:

P(n): 6ⁿ + 4 is divisible by 5

It will be proved that P(n) is true for each n ∈ N.

• Initial step:

Will show P(1) is true
6¹ + 4 = 10 is divisible by 5

So, P(1) is true

• Induction step:

Imagine that P(k) is true, namely:
6^k + 4 is divisible by 5, k ∈ N

This will show that P(k + 1) is also true, namely:
6^k+1 + 4 is divisible by 5.

6^k+1 + 4 = 6(6^k)+ 4
6^k+1 + 4 = 5(6^k) + 6^k + 4

Cause 5(6^k) is divisible by 5 and 6^k + 4 is divisible by 5, so 5(6^k) + 6^k + 4 is also divisible by 5.

So, P(k + 1) is true.

Based on the principle of mathematical induction, it is proven that 6ⁿ + 4 is divisible by 5, for each n natural number.

Integer a will be divisible by integer b when integer m is found, so that a = bm will apply.

For example, "10 is divisible by 5" is true because there are integers m = 2 so 10 = 5.2.

Therefore, the statement "10 is divisible by 5" can be written as "10 = 5m, for m integers"

Based on the above concept, the division proof can also be solved using the following method.

• Example 2:

Prove n³ + 2n will be divisible by 3, for each n natural number

Answer:

P(n): n³ + 2n = 3m, with m ∈ ZZ

It will be proved that P(n) is true for each n ∈ NN

• Initial step:

It will be shown that P(1) is true
1³ + 2.1 = 3 = 3.1

So, P(1) is true

• Induction step:

Imagine that P(k) is true, namely:
k³ + 2k = 3m, k ∈ NN

This will show that P(k + 1) is also true, namely:
(k + 1)³ + 2(k + 1) = 3p, p ∈ ZZ

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

Since m is an integer and k is a natural number, then (m + k² + k + 1) is an integer.

For example p = (m + k² + k + 1), so:
(k + 1)³ + 2(k + 1) = 3p, with p ∈ ZZ

So, P(k + 1) is true

Based on the concept of mathematical induction above, it is proven that n³ + 2n will be divisible by 3, for each n natural number.

---

Proof of Inequality

The following are some of the properties of inequalities that are often used, including:

1. transitive nature
a > b > c ⇒ a > c or
a < b < c ⇒ a < c

2. a < b and c > 0 ⇒ ac < bc or
a > b and c > 0 ⇒ ac > bc

3. a < b ⇒ a + c < b + c or
a > b ⇒ a + c > b + c

Before we get into the example questions, it's a good idea to practice using the properties above to show the implication "if P(k) is true, then P(k + 1) is also true".

Example

P(k): 4k < 2^k
P(k + 1): 4(k + 1) < 2^k+1

If it is assumed that P(k) is true for k ≥ 5, then show that P(k + 1) is also true!

Remember that our target is to show, so:
4(k + 1) < 2^k+1 = 2(2^k) = 2^k + 2^k (TARGET)

We can start from the left-hand side of the inequality above to:
4(k + 1) = 4k + 4
4(k + 1) < 2^k + 4 (because 4k < 2^k)
4(k + 1) < 2^k + 2^k (because 4 < 4k < 2^k)
4(k + 1) = 2(2^k)
4(k + 1) = 2^k+1

Based on the transitive nature, we can conclude that 4(k + 1) < 2^k+1

Why 4k can change to 2^k ?

Because according to property 3, we are allowed to add both sides of an inequality by the same number.

Because it will not change the truth value of the inequality. Because 4k < 2^k true, which results in 4k + 4 < 2^k + 4 is also true.

How do we know that 4 must be changed to 2^k ?

Watch the targets.

The temporary result we get is 2^k + 4 while our target is 2^k + 2^k.

For k ≥ 5, then 4 < 4k and 4k < 2^k that is true, so 4 < 2^k is also true (transitive property). This results in 2^k + 4 < 2^k + 2^k true (property 3).

Problems example

Problem1

Prove that for each natural number n ≥ 4 and holds
3n < 2ⁿ

Answer:

P(n): 3n < 2ⁿ

It will be proved that P(n) holds for n ≥ 4, n ∈ NN

Will show that P(4) is true
3.4 = 12 < 2⁴ = 16

So, P(4) is true

Imagine that P(k) is true, namely:
3k < 2^k, k ≥ 4

This will show that P(k + 1) is also true, namely:
3(k + 1) < 2^k+1

3(k + 1) = 3k + 3
3(k + 1) < 2^k + 3 (because 3k < 2^k)
3(k + 1) < 2^k + 2^k (since 3 < 3k < 2^k)
3(k + 1) = 2(2^k)
3(k + 1) = 2^k+1

So, P(k + 1) is also true.

Based on the concept of mathematical induction, it is proven that P(n) holds for each natural number n ≥ 4.

Problem 2

Prove that .

Discussion:

• Step 1

(proven)

• Step 2 (n = k)

• Step 3 (n = k + 1)

.

(both fields added .

{proven).

Problem 3

Prove that for each natural number n ≥ 2 and holds 3ⁿ > 1 + 2n

Answer:

P(n): 3ⁿ > 1 + 2n

It will be proved that P(n) holds for n ≥ 2, n ∈ NN

Will show that P(2) is true, namely:
3² = 9 > 1 + 2.2 = 5

So, P(1) is true

Imagine that P(k) is true, namely:
3^k > 1 + 2k, k ≥ 2

Will find that P(k + 1) is also true, ie
3^k+1 > 1 + 2(k + 1)

3^k+1 = 3(3^k)
3^k+1 > 3(1 + 2k) (because 3^k >1+2k)
3^k+1 = 3 + 6k
3^k+1 > 3 + 2k (because 6k > 2k)
3^k+1 = 1 + 2k + 2
3^k+1 = 1 + 2(k + 1)

So, P(k + 1) is also true

Based on the concept of mathematical induction, it is proven that P(n) holds for each natural number n ≥ 2.

Prove that

Discussion:

• Step 1

(proven)

• Step 2 (n = k)

• Step 3 (n = k + 1)

Proven by:

(both sides multiplied )

(2^k modified to 2^k+1)

(proven)

Problem 4

Prove that for each natural number n ≥ 5 it will hold 2n − 3 < 2^n-2

Answer:

P(n): 2n − 3 < 2^n-2

It will be proved that P(n) holds for n ≥ 5, n ∈ NN

It will be shown that P(5) is true
2.5 − 3 = 7 < 2^5-2 = 8

So, P(1) is true

Imagine that P(k) is true, namely:
2k − 3 < 2^k-2, k ≥ 5

This will show that P(k + 1) is also true, namely:
2(k + 1) − 3 < 2^k+1-2

2(k + 1) − 3 = 2k + 2 − 3
2(k + 1) − 3 = 2k − 3 + 2
2(k + 1) − 3 < 2^k-2 + 2 (because 2k − 3 < 2^k-2)
2(k + 1) − 3 < 2^k-2 + 2^k-2 (because 2 < 2k − 3 < 2^k-2)
2(k + 1) − 3 = 2(2^k-2)
2(k + 1) − 3 = 2^k+1-2

So, P(k + 1) is also true

Based on the concept of mathematical induction, it is proven that P(n) holds for each natural number n ≥ 5.

Problem 5:

Prove that for each natural number n ≥ 4 and hold (n + 1)! > 3ⁿ

Answer:

P(n): (n + 1)! > 3ⁿ

It will be proved that P(n) holds for n ≥ 4, n ∈ NN

Will show P(4) is true
(4 + 1)! > 3⁴
left side: 5! = 5.4.3.2.1 = 120
right side: 3⁴ = 81

So, P(1) is true

Imagine that P(k) is true, namely:

(k+1)! > 3^k, k ≥ 4

It will be shown that P(k + 1) is also true, ie
(k + 1 + 1)! > 3^k+1

(k + 1 + 1)! = (k + 2)!
(k + 1 + 1)! = (k + 2)(k + 1)!
(k + 1 + 1)! > (k + 2)(3^k) (because (k + 1)! > 3^k)
(k + 1 + 1)! > 3(3^k) (because k + 2 > 3)
(k + 1 + 1)! = 3^k+1

So, P(k + 1) is also true.

Based on the concept of mathematical induction, it is proven that P(n) holds for each natural number n ≥ 4.

Thus the review from About the knowledge.co.id about Mathematical Induction , hopefully can add to your insight and knowledge. Thank you for visiting and don't forget to read other articles