# Thread: Mathematical Induction - Inequalities

1. ## Mathematical Induction - Inequalities

Code:
Prove that 3^n>2n^2-1 for all positive integers n via mathematical induction.
After proving the above inequality is true for n=1, I assume P(k): 3^k>2k^2-1 is true, and P(k+1):3(3^k)>3(2k^2-1). Then I'd need to prove that 3(2k^2-1) is greater than 2(k+1)^2-1. If I work backwards and do expand along these lines, I end up with a quadratic equation k^2-k-1>0 where the ranges k>1.618 and k<-0.618 satisfy the aforementioned inequality. However, since k is defined to be greater than 1, this does not compute for k>1.618.

I'm guessing since I've proven that P(n) is true for n=1 earlier, and since by definition n is an integer (hence the next integer value for n would be 2), hence k is true for 2 since 2>1.618. Is this necessarily true or am I missing something here?

2. Originally Posted by smmxwell
I'm guessing since I've proven that P(n) is true for n=1 earlier, and since by definition n is an integer (hence the next integer value for n would be 2), hence k is true for 2 since 2>1.618. Is this necessarily true or am I missing something here?

The inequaly is true for $\displaystyle n=1,2$ by simple substitution. Now, for the induction step:

$\displaystyle P(n)\Rightarrow P(n+1)$

for all $\displaystyle n\geq 2$ .

3. Originally Posted by FernandoRevilla
The inequaly is true for $\displaystyle n=1,2$ by simple substitution. Now, for the induction step:

$\displaystyle P(n)\Rightarrow P(n+1)$

for all $\displaystyle n\geq 2$ .
Yes. That was what I meant to write. Since n is equal or greater to 1, hence n+ is greater or equal to 2. So, I'd proceed as usual, and conclude that P(n) is true? Thanks! Consider this thread solved than.

4. Originally Posted by smmxwell
Code:
Prove that 3^n>2n^2-1 for all positive integers n via mathematical induction.
After proving the above inequality is true for n=1, I assume P(k): 3^k>2k^2-1 is true, and P(k+1):3(3^k)>3(2k^2-1). Then I'd need to prove that 3(2k^2-1) is greater than 2(k+1)^2-1. If I work backwards and do expand along these lines, I end up with a quadratic equation k^2-k-1>0 where the ranges k>1.618 and k<-0.618 satisfy the aforementioned inequality. However, since k is defined to be greater than 1, this does not compute for k>1.618.

I'm guessing since I've proven that P(n) is true for n=1 earlier, and since by definition n is an integer (hence the next integer value for n would be 2), hence k is true for 2 since 2>1.618. Is this necessarily true or

am I missing something here ?
Yes, you are missing something!

You are attempting to show that P(k+1) will be true "if" P(k) is true.

Therefore, "if" P(k) is true, you only need show that $\displaystyle 3^{k+1}>2(k+1)^2-1$ also.

You decided that since $\displaystyle 3\left(3^k\right)>3\left(2k^2-1\right)$ if P(k) is true,

then it should be enough to show $\displaystyle 3\left(2k^2-1\right)\ge\ 2(k+1)^2-1$

This logic is incomplete, though with some tweaking (moving to k>2 for example) it's ok.
If the above line was clearly true, then everything's fine
but that line may not necessarily be true for all relevant k.

What you may do instead is...

$\displaystyle 3^{k+1}>2(k+1)^2-1\;\;\;?$

This is the P(k+1) proposition. Try to show that this will be true if P(k) is true.

$\displaystyle (3)3^k>2k^2+4k+1\;\;\;?$

$\displaystyle 3^k+(2)3^k>2k^2-1+4k+2\;\;\;?$

If P(k) is true, we are left with

$\displaystyle (2)3^k\ge\ 4k+2\;\;?$

$\displaystyle 3^k\ge\ 2k+1\;\;?$