I can that this is showing $\displaystyle 2^{N+1}\geq 4(N+1)$. But I can't see how this equality is equal to $\displaystyle 2^{N}$ or $\displaystyle 4N + 4N > 4N + 4 = 4(N+1)$

Printable View

- May 21st 2012, 09:12 AMalyosha2Re: Proving inequality through induction
I can that this is showing $\displaystyle 2^{N+1}\geq 4(N+1)$. But I can't see how this equality is equal to $\displaystyle 2^{N}$ or $\displaystyle 4N + 4N > 4N + 4 = 4(N+1)$

- May 21st 2012, 09:52 AMalyosha2Re: 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 AMalyosha2Re: 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)

$\displaystyle 2^k - 4k$

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

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

$\displaystyle > 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 $\displaystyle 4k$ is less than $\displaystyle 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 $\displaystyle 2^k - 4k < 0$ then the difference left by $\displaystyle 2^{k+1} - 4(k+1) > 0$.

How can we do this?

Well we use $\displaystyle 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 $\displaystyle 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 $\displaystyle 2^k$ to become $\displaystyle 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 $\displaystyle 2 * 2^k - 4(k+1) < 2 * 4k - 4(k+1)$

The left hand side of this equality simplifes to $\displaystyle 8k - 4k - 4$ and then to $\displaystyle 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 AMDevenoRe: 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 2^{n}> 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:

2^{5}= 32, and this is indeed greater than 4*5 = 20.

now, IF 2^{n}> 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 2^{n}> 4n, PROVE that 2^{n+1}> 4(n+1).

now an equivalent way of stating this, is:

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

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

2^{n+1}- 4(n+1) = 2(2^{n}) - 4(n+1).

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

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

2^{n+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 2^{n+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 2^{n+1}- 4(k+1) > 4n - 4, and n - 4 > 0,

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

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

we have "completed the induction", and shown the inequality holds for all natural numbers greater than 4.