Mathematical Induction Step

In summary: The key is to use the properties of inequalities and the inductive hypothesis to show that the statement holds for n+1, given that it holds for n. This extra inequality is not necessary in this case.In summary, the key to using mathematical induction to prove inequalities is to first prove the basis step and then use the inductive hypothesis to show that the statement holds for n+1, given that it holds for n. There is no need for any additional inequalities, as the properties of inequalities and the inductive step are sufficient to prove the statement.
  • #1
beatem
5
0
Hi,

I'm trying to learn mathematical induction for proving inequalities, but there is just one step I cannot get past: finding another inequality that is added to the inductive hypothesis.

For example, in this problem:

Prove for all positive integers (n >= 1), prove 3^n + 2 >= 3n.

I understand the basis step and in general how to do induction, but for some reason, the example says that that after I get the hypothesis, 3^k + 2 >= 3k (for some arbitrary k), it can generate the inequality 2*3^k >= 3 for all k >= 1. Where does this come from? I can follow how it adds this inequality to the hypothesis, but what is this, and how would I go about getting this?

This isn't just a generic problem by the way: I've looked at many examples, but I can't figure out what this is when dealing with inequalities and induction.
 
Mathematics news on Phys.org
  • #2
For your example I would first show: 3n ≥ 3n which is easier.
You said you can do the basic step. So let's move on to the induction.

To do the induction we suppose n, then we prove if n is true, n+1 is true.
So first suppose: 3n ≥ 3n. Then our goal is to show: 3n+1≥3(n+1)

To do that I would prove the following:
3n ≥ 3n ⇒ 3+3n ≥ 3(n+1)
Then i would prove: 3n+1≥3+3n for n>1
Putting these together: 3n+1≥3+3n≥3(n+1) This step shows our goal!
Thus by the principle of induction: 3n ≥ 3n for Natural n

Then you know: 3n ≥ 3n ⇒3n + 2 ≥ 3n or 3n ≥ 3n ⇒3*3*3n =3n+2 ≥ 3n from the properties of inequalities. It's hard to tell which of these you were trying to prove how you wrote it.
 
Last edited:
  • #3
Thanks for the reply!

Sorry: I meant (3^n)+2

So is there no need for the extra inequality of 2*3^n >= 3? Or am I just missing something?
 
  • #4
No need for the other inequality, which i think you typed incorrectly.
 
  • #5


I can understand your confusion with this concept. Mathematical induction can be a challenging topic to grasp, especially when it comes to proving inequalities. Let me try to break down the process for you and hopefully it will become clearer.

First, let's review the steps of mathematical induction. The first step, as you mentioned, is the basis step where we prove the statement for the first value of n (in this case n=1). The second step is the inductive hypothesis, where we assume that the statement is true for some arbitrary value of n (in this case k). And finally, the third step is the inductive step, where we need to prove that the statement is true for the next value of n (in this case k+1).

Now, in order to prove the statement 3^n + 2 >= 3n for all positive integers n, we need to follow these steps. For the inductive hypothesis, we assume that the statement is true for some arbitrary value of n (in this case k). So, we can write it as 3^k + 2 >= 3k. Now, for the inductive step, we need to prove that the statement is true for the next value of n, which is k+1. This means we need to prove that 3^(k+1) + 2 >= 3(k+1).

To do this, we can use the inductive hypothesis. We know that 3^k + 2 >= 3k, so we can replace 3^k with 3k in the expression 3^(k+1) + 2 to get 3^(k+1) + 2 >= 3k + 2. Now, we need to show that 3k + 2 >= 3(k+1). This is where the inequality 2*3^k >= 3 (for all k>=1) comes in. If we multiply both sides of the inequality 3k + 2 >= 3 with 3, we get 3(3k + 2) >= 3*3. Simplifying this, we get 3^(k+1) + 6 >= 9. And since we know that 3^(k+1) + 2 >= 3k + 2, we can replace 3^(k+1) + 6 with 3^(k
 

1. What is the purpose of the mathematical induction step?

The mathematical induction step is used to prove that a statement holds for all natural numbers. It is an important tool in mathematical proofs, particularly in proving theorems and solving problems involving sequences and series.

2. How does the mathematical induction step work?

The mathematical induction step follows a two-step process. First, the base case is established by showing that the statement holds for the first natural number. Then, the induction hypothesis is used to show that if the statement holds for a particular natural number, it also holds for the next natural number. This process is repeated for all subsequent natural numbers, proving that the statement holds for all natural numbers.

3. What is the difference between strong and weak induction?

In strong induction, the induction hypothesis assumes that the statement holds for all natural numbers up to and including the current one. In weak induction, the induction hypothesis only assumes that the statement holds for the current natural number.

4. Can mathematical induction be used to prove all mathematical statements?

No, mathematical induction can only be used to prove statements that hold for all natural numbers. It cannot be used to prove statements that only hold for a finite or infinite subset of natural numbers, or statements that involve real numbers.

5. Are there any common mistakes when using mathematical induction?

Yes, some common mistakes when using mathematical induction include only proving the statement for a specific natural number instead of all natural numbers, assuming the statement holds for all natural numbers without proving it, and using circular reasoning to prove the statement.

Similar threads

Replies
13
Views
1K
Replies
5
Views
2K
Replies
2
Views
1K
Replies
1
Views
1K
  • General Math
Replies
10
Views
1K
  • General Math
Replies
7
Views
3K
Replies
7
Views
2K
  • General Math
Replies
1
Views
1K
  • General Math
Replies
26
Views
4K
Back
Top