Thread: Proving inequality through induction

I can that this is showing . But I can't see how this equality is equal to or

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?

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)







using





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 .

This means that if is less than 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 then the difference left by .

How can we do this?

Well we use to express the difference of the proposition with k+1 and note that this can be expressed in terms of k as .

Now if we assume that 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 to become and then do the same to the other the other side of the inequality to maintain equality with original.

So

The left hand side of this equality simplifes to and then to 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.

you have some errors in your proof, but the idea is almost right.

we want to prove that if n > 4, then 2ⁿ > 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⁵ = 32, and this is indeed greater than 4*5 = 20.

now, IF 2ⁿ > 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ⁿ > 4n, PROVE that 2ⁿ⁺¹ > 4(n+1).

now an equivalent way of stating this, is:

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

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

2ⁿ⁺¹ - 4(n+1) = 2(2ⁿ) - 4(n+1).

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

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

2ⁿ⁺¹ - 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ⁿ⁺¹ - 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ⁿ⁺¹ - 4(k+1) > 4n - 4, and n - 4 > 0,

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

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

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