# Induction of inequality

Printable View

• Sep 13th 2012, 09:45 AM
dowant
Induction of inequality
I am having a hard time getting started on this.

n*3n<= 4n-2
where n>6

I have done the start step setting n = 7 and affirming that it is true.

and I assume

k*3k<= 4k-2

but I cannot grasp how I should prove
(k+1)*3(k+1)<= 4(k+1)-2

Thank you
• Sep 13th 2012, 10:53 AM
DeMath
Re: Induction of inequality
Your inequality is very similar to the Bernoulli's inequality.
• Sep 13th 2012, 12:57 PM
dowant
Re: Induction of inequality
I fail to see how.
• Sep 13th 2012, 01:31 PM
Plato
Re: Induction of inequality
Quote:

Originally Posted by dowant
n*3n<= 4n-2 where n>6
I have done the start step setting n = 7 and affirming that it is true.
and I assume
k*3k<= 4k-2

Start from the above.
\displaystyle \begin{align*}(k+1)3^{k+1}&=(3k+3)3^k \\&\le (3k+3)(4^k-2) \end{align*}
• Sep 13th 2012, 01:57 PM
emakarov
Re: Induction of inequality
This can be proved using the auxiliary fact

$\displaystyle 3^{n+1}\le4^n$ for $\displaystyle n\ge4$ (*)

It is easily proved by induction.

\displaystyle \begin{align*}(n+1)\cdot3^{n+1}&=3n\cdot 3^n+3^{n+1}\\ &\le3(4^n-2)+3^{n+1}&&\text{by IH}\\ &<3\cdot 4^n-2+3^{n+1}\\ &<3\cdot4^n+4^n-2&&\text{by (*))}\\ &=4^{n+1}-2 \end{align*}