Proving inequality through induction

**alyosha2** · May 21st 2012, 05:21 AM

$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.

**Prove It** · May 21st 2012, 05:28 AM

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...

**alyosha2** · May 21st 2012, 05:42 AM

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.

**Prove It** · May 21st 2012, 06:13 AM

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.

**alyosha2** · May 21st 2012, 07:04 AM

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.

**Plato** · May 21st 2012, 07:50 AM

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*}$

**alyosha2** · May 21st 2012, 08:19 AM

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.

**Plato** · May 21st 2012, 08:26 AM

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&~?$

**alyosha2** · May 21st 2012, 08:29 AM

Originally Posted by Plato

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

yes.

**Plato** · May 21st 2012, 08:34 AM

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?

**alyosha2** · May 21st 2012, 08:38 AM

yes.

**Plato** · May 21st 2012, 08:44 AM

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)$

**alyosha2** · May 21st 2012, 08:51 AM

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?

**Plato** · May 21st 2012, 08:56 AM

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.

**alyosha2** · May 21st 2012, 09:01 AM

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.

Thread: Proving inequality through induction

LinkBack

Thread Tools

Display

Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Re: Proving inequality through induction

Similar Math Help Forum Discussions

Induction: an inequality

Induction Inequality

Proving the triangle inequality using the Cauchy-Schwartzs inequality

Induction for an inequality

induction inequality

Search Tags