# Proving inequality through induction

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• May 21st 2012, 05:21 AM
alyosha2
Proving inequality through induction
$2^k > 4k$

$2^k > 4k = 2^k - 4k < 0$

$2^{k+1}-4(k+1) = 2 x 2^k -4(k+1)$
$> 2 x 4k - 4(k+1)$, using $2^k > 4^k,$
$=8k -4k - 4 = 4k -4$

I don't understand what has happened in the second to last step here.
• May 21st 2012, 05:28 AM
Prove It
Re: Proving inequality through induction
It's not true. Try k = 2, we have \displaystyle \begin{align*} 2^2 = 4 \end{align*} and \displaystyle \begin{align*} 4 \cdot 2 = 8 \end{align*}, so the inequality does not hold...
• May 21st 2012, 05:42 AM
alyosha2
Re: Proving inequality through induction
The text says "This expression is greater than 0 for K > 1. So Proof by mathematical induction works, except we cannon start at n = 1."

I just don't follow the working.
• May 21st 2012, 06:13 AM
Prove It
Re: Proving inequality through induction
I have just proved to you that the inequality is not true. Arguing that it is will not change that. Either state that \displaystyle \begin{align*} k \geq 5 \end{align*} or stop trying.
• May 21st 2012, 07:04 AM
alyosha2
Re: Proving inequality through induction
Yes sorry I should have stated that k has to be equal to or larger than 5. I didn't mean to try to argue with you. It's just that I'm trying to understand what is happening in the second to last step in the working. I can't see how the expression on the left is converted into an equality and then what it means to have an equality there.
• May 21st 2012, 07:50 AM
Plato
Re: Proving inequality through induction
Quote:

Originally Posted by alyosha2
Yes sorry I should have stated that k has to be equal to or larger than 5.

Because $2^5>4\cdot 5$, the base case it true.

Suppose that $N>5$ and $2^N>4\cdot N$.
\begin{align*}2^{N+1}=2\cdot 2^N&\ge 2(4\cdot N)\\&= (4\cdot N)+ (4\cdot N)\\&\ge 4(N+1)\end{align*}
• May 21st 2012, 08:19 AM
alyosha2
Re: Proving inequality through induction
Quote:

Originally Posted by Plato
Because $2^5>4\cdot 5$, the base case it true.

Suppose that $N>5$ and $2^N>4\cdot N$.
\begin{align*}2^{N+1}=2\cdot 2^N&\ge 2(4\cdot N)\\&= (4\cdot N)+ (4\cdot N)\\&\ge 4(N+1)\end{align*}

I'm sorry I don't understand

how does $2^{N+1}=2\cdot 2^N&\ge 2(4\cdot N)$ How does an integer equal an equality?

how do you get from this line to the last?

How does this relate to the original working I posted?

I'm trying to understand how we go from an integer expression to an equality and then back again and how I am supposed to understand the meaning of this equality. To put it simply one equals a number and the other is true or false so how can they be equal?

Thanks.
• May 21st 2012, 08:26 AM
Plato
Re: Proving inequality through induction
Quote:

Originally Posted by alyosha2
I'm sorry I don't understand
how does $2^{N+1}=2\cdot 2^N&\ge 2(4\cdot N)$ How does an integer equal an equality?

One step at a time.
1) Do you understand $2^{N+1}=2\cdot 2^N&~?$
• May 21st 2012, 08:29 AM
alyosha2
Re: Proving inequality through induction
Quote:

Originally Posted by Plato
One step at a time.
1) Do you understand $2^{N+1}=2\cdot 2^N&~?$

yes.
• May 21st 2012, 08:34 AM
Plato
Re: Proving inequality through induction
Quote:

Originally Posted by alyosha2
yes.

OK then:
2) the inductive step says if $N>5$ then $2^N>4\cdot N$.
Therefore $2\cdot 2^N>2(4\cdot N)$. Do you see that?
• May 21st 2012, 08:38 AM
alyosha2
Re: Proving inequality through induction
yes.
• May 21st 2012, 08:44 AM
Plato
Re: Proving inequality through induction
Quote:

Originally Posted by alyosha2
yes.

Good. 3)
$2(4\cdot N)=4\cdot N+4\cdot N$

But $4\cdot N>4$

So $4\cdot N+4\cdot N>4\cdot N+4=4(N+1)$
• May 21st 2012, 08:51 AM
alyosha2
Re: Proving inequality through induction
I'm sorry I don't see how we go from an equality on the left to an number on the right.

Also, what is the significance of 4N being larger than 4?
• May 21st 2012, 08:56 AM
Plato
Re: Proving inequality through induction
Quote:

Originally Posted by alyosha2
I'm sorry I don't see how we go from an equality on the left to an number on the right.
Also, what is the significance of 4N being larger than 4?