# Proving inequality through induction

Printable View

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
$\displaystyle 2^k > 4k$

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

$\displaystyle 2^{k+1}-4(k+1) = 2 x 2^k -4(k+1)$
$\displaystyle > 2 x 4k - 4(k+1)$, using $\displaystyle 2^k > 4^k,$
$\displaystyle =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 \displaystyle \begin{align*} 2^2 = 4 \end{align*} and \displaystyle \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 \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 $\displaystyle 2^5>4\cdot 5$, the base case it true.

Suppose that $\displaystyle N>5$ and $\displaystyle 2^N>4\cdot N$.
\displaystyle \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 $\displaystyle 2^5>4\cdot 5$, the base case it true.

Suppose that $\displaystyle N>5$ and $\displaystyle 2^N>4\cdot N$.
\displaystyle \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 $\displaystyle 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 $\displaystyle 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 $\displaystyle 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 $\displaystyle 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 $\displaystyle N>5$ then $\displaystyle 2^N>4\cdot N$.
Therefore $\displaystyle 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)
$\displaystyle 2(4\cdot N)=4\cdot N+4\cdot N$

But $\displaystyle 4\cdot N>4$

So $\displaystyle 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?

Well think about it.

I don't think you are ready to do this question.
• May 21st 2012, 09:01 AM
alyosha2
Re: Proving inequality through induction
Well an equality has a Boolean value that is either true of false. So the left hand side of the equation must be equal to one of two values. True of False. The expression on the right hand side is a number. How can you equate them?

You obviously can because that is what you are doing I just don't understand how you are doing it.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last