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

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

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

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

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

6. Re: Proving inequality through induction

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

7. Re: Proving inequality through induction

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.

8. Re: Proving inequality through induction

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

9. Re: Proving inequality through induction

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

10. Re: Proving inequality through induction

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?

yes.

12. Re: Proving inequality through induction

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

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

14. Re: Proving inequality through induction

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?

I don't think you are ready to do this question.

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

Page 1 of 2 12 Last