# Proving inequality through induction

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• May 21st 2012, 09:12 AM
alyosha2
Re: Proving inequality through induction
I can that this is showing $2^{N+1}\geq 4(N+1)$. But I can't see how this equality is equal to $2^{N}$ or $4N + 4N > 4N + 4 = 4(N+1)$
• May 21st 2012, 09:52 AM
alyosha2
Re: Proving inequality through induction
I understand now the equality sign only applies to the expression on the side of the inequality sign on which it is placed, rather than equating the whole inequality expression.

Given the explanation posted in the thread I'm still confused about why the working I have posted gives the inequality to larger than 4k - 4 rather than 4(K+1).

Is this something to do with the shifting of the inequality sign?

Why have they chosen to express the ineqaulity sign as they have?
• May 22nd 2012, 05:33 AM
alyosha2
Re: Proving inequality through induction
After many hours of intense thought I came to a solution and thought I should post it so as to not to leave the thread without clousre in case someone has a similar problem. Also I hope it will help crystallise the idea for me and perhaps I've even got it wrong so others could refine it.

First a word about precedence and equality signs. It's usual to think of the equality sign as having the lowest possible precedence.This however is not the case when considering inequality signs which appear to have an even lower precedence than equality signs. So a = b > c = d is (a = b) > (c = d) or just b > c and not a = (b > c) = d.

So, to my original problem

(fixed some errors)

$2^k - 4k$

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

$2^{k+1} - 4(k+1) = 2 * 2^{k} - 4(k+1)$

$> 2 * 4k - 4(k+1)$ using http://latex.codecogs.com/png.latex?...20%3E%204%5Ek,

http://latex.codecogs.com/png.latex?...%20=%204k%20-4

Now the idea here was to show by induction that this inequality would hold for large enough values of n. It was noted that If the inequality held this would mean that http://latex.codecogs.com/png.latex?...204k%20%3C%200.

This means that if $4k$ is less than $2^k$ then subtracting the smaller from the larger would leave a difference that is larger than 0.

Now to show that the equality will hold we will have to show that if the difference left by $2^k - 4k < 0$ then the difference left by $2^{k+1} - 4(k+1) > 0$.

How can we do this?

Well we use $2^{k+1} - 4(k+1)$ to express the difference of the proposition with k+1 and note that this can be expressed in terms of k as $2 * 2^{k} - 4(k+1)$.

Now if we assume that http://latex.codecogs.com/png.latex?2%5Ek%20%3E%204k we can use this inequality to find an expression that the difference of the proposition with (K+1) will be larger than and if this expression is larger than 0 we know the proposition will hold.

We do this by manipulating the left side of the inequality $2^k$ to become $2 * 2^{k} - 4(k+1)$ and then do the same to the other the other side of the inequality to maintain equality with original.

So $2 * 2^k - 4(k+1) < 2 * 4k - 4(k+1)$

The left hand side of this equality simplifes to $8k - 4k - 4$ and then to $4k - 4$ and this expression will equate to greater than 0 for k > 1. So we know that the proposition will hold for some value k > 1.

This is my understanding and it seems satisfactory as far as I can tell. Please let me know if I have made any wrong assumptions or have completely misunderstood.

Thanks.
• May 22nd 2012, 09:13 AM
Deveno
Re: Proving inequality through induction
you have some errors in your proof, but the idea is almost right.

we want to prove that if n > 4, then 2n > 4n.

we want to prove this for all natural numbers greater than 4. the "way" we do this is prove it for n = 5, and then show:

true for n implies true for n+1.

putting these two facts together gives us:

true for 5 implies true for 6 implies true for 7 implies true for 8 implies....(and so on, forever).

which is the same as saying "true for all n > 4".

it is important we not neglect the "base case", here, it is n = 5:

25 = 32, and this is indeed greater than 4*5 = 20.

now, IF 2n > 4n for some natural number n (greater than 4), we'd like to prove the statement is also true for "the next number" n+1.

that is, GIVEN that 2n > 4n, PROVE that 2n+1 > 4(n+1).

now an equivalent way of stating this, is:

given 2n - 4n > 0, prove 2n+1 - 4(n+1) > 0.

so starting with the expression 2n+1 - 4(n+1), we observe that:

2n+1 - 4(n+1) = 2(2n) - 4(n+1).

and since 2n > 4n (our given assumption, or induction hypothesis)

we know that 2(2n) > 2(4n), and 2(4n) = 8n. so

2n+1 - 4(n+1) > 8n - 4(n+1).

but 4(n+1) = 4n + 4, so 8n - 4(n+1) = 8n - 4n - 4 = 4n - 4.

so so far we know that 2n+1 - 4(n+1) > 4n - 4.

but we also know that n > 4, so that 4n > 16, so 4n - 4 > 16 - 4, and of course 16 - 4 = 12.

using the transitivity of "greater than" ( that is if a > b and b > c, then a > c), and the fact that 12 > 0, we have from:

n > 4, that 4n - 4 > 12 > 0, so 4n - 4 > 0 (for any n > 4. it's also true for "other smaller n", but smaller values aren't of interest to us, because we're only proving our "main result" for n > 4).

then we have from 2n+1 - 4(k+1) > 4n - 4, and n - 4 > 0,

that 2n+1 - 4(n+1) > 0, and therefore that:

2n+1 > 4(n+1). and since that was what we set out to prove from our start of the assumption that 2n > 4n,

we have "completed the induction", and shown the inequality holds for all natural numbers greater than 4.
Show 40 post(s) from this thread on one page
Page 2 of 2 First 12