Mathematical induction: Prove that 2^n > 3n for all n>

[owenthakkar]

hey guys!! can anyone help me with this hard question?
its to do with mathematical induction (inequalitites)
i think im missing a step in my proof and i just cant figure it out.... :?

heres the question:

Prove that 2^n>3n for all positive integers where n is greater than or equal to 4

thanks guys
any help would be great

 

[pka]

Clearly it is true for n=4, $\displaystyle 16 = 2^4 > 12 = \left( 3 \right)\left( 4 \right)$.
So we are on the path. Suppose we can get to the Kth step, that is
$\displaystyle 2^K > \left( 3 \right)\left( K \right)$ is true.

Now look at $\displaystyle 2^{K+1}$.
We have \(\displaystyle \begin{array}{rcl}
2^{K + 1} & = & 2\left( {2^K } \right) \\
& > & 2\left( 3 \right)\left( K \right) \\
& = & \left( 3 \right)\left( {2K} \right) \\
& = & \left( 3 \right)\left( {K + K} \right) \\
& > & \left( 3 \right)\left( {K + 1} \right) \\
\end{array}\)

So we can go from the Kth place to the (K+1)th place.

 

[soroban]

Re: Mathematical induction: Prove that 2^n > 3n for all n

Hello, owenthakkar!

Here's my approach . . .

Prove that $\displaystyle 2^n\:>\:3n$ for all positive integers where $\displaystyle n\,\geq\,4$

Note: for $\displaystyle n\,\geq\,4,\;2^n\:>\: 3$


First, verify $\displaystyle S(1).$


Then assume $\displaystyle S(k):\;\;2^k \;>\; 3k$

$\displaystyle \;\;$Add $\displaystyle 2^k$ to both sides: $\displaystyle \:2^k\,+\,2^k\;> \;3k\,+\,2^k$

The left side is: $\displaystyle \,2^k\,+\,2^k\;=\;2\cdot2^k\;=\;2^{k+1}$

$\displaystyle \;\;$So we have: $\displaystyle \,2^{k+1}\;>\;3k\,+\,2^k$


Since $\displaystyle 2^k\,>\,3$, we have: $\displaystyle \,2^{k+1}\;>\;3k\,+\,2^k\;>\;3k\,+\,3$

$\displaystyle \;\;$Therefore: $\displaystyle \,2^{k+1}\;>\:3(k\,+\,1)$