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.

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

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.

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.

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.

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

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.

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

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.

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?

Re: Proving inequality through induction

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

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?

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.

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.