You are Here: Home >< Maths

# P6 induction watch

1. Given that n is a postive integer greater than two, use the method of mathematical induction to prove that 2^n > 2n.

Thanks guys
2. (Original post by SUKBarracuda)
Given that n is a postive integer greater than two, use the method of mathematical induction to prove that 2^n > 2n.

Thanks guys
For n=3,
2^3 > 2*3
8 > 6

For n=(k+1)
2^(k+1) > 2(k+1)
2^k > k+1

I think that's enough to prove it, though it's the first induction I've ever tried so don't take my word for it.
3. Im a little rusty at the old induction, but here goes:

Initial Step

Let n=3

Then 2^3 > 2 * 3

Which is TRUE

Induction Step

Assume truth of case when n = k

ie 2^k > 2k

Then we wish to prove the truth of case when n= (k+1)

ie 2^(k+1) > 2(k+1)

2^(k+1) = (2^k)*(2) *Law of Indices: x^a * x^b = x^(a+b)*

2(k+1) = 2k + 2
when k > 2 , 2* (2^k) > 2k + 2

So assertion is true for n = k + 1, and so by Mathematical Induction is proved for all positive integers n, with n > 2.

Note: Induction step slightly messy.
4. Let n be a positive integer. Suppose that 2^n > 2n. Then

2^(n + 1)
= 2 * 2^n
> 2 * 2n . . . by the inductive hypothesis
= 4n
= 2(n + 1) + 2(n - 1)
>= 2(n + 1) . . . because n >= 1.

So 2^(n + 1) > 2(n + 1).
5. I offer rep for the first person who proves by induction that there is an integer K such that, for all k >= K,

2^k > k^10.
6. (Original post by Jonny W)
Let n be a positive integer. Suppose that 2^n > 2n. Then

2^(n + 1)
= 2 * 2^n
> 2 * 2n . . . by the inductive hypothesis
= 4n
= 2(n + 1) + 2(n - 1)
>= 2(n + 1) . . . because n >= 1.

So 2^(n + 1) > 2(n + 1).

I don't doubt your solution, infact it looks quite cushy, but how did we get from

2^(n+1) = 2 * (2^n) (which I'm fine with) > 2* 2n
7. [Initial Step]

Let n > limiting value (2)

2^3 > 2(3) ? yes

Let n = k and assume true

2^k > 2k is true [A]

[Induction]

k --> k+1

2^(k+1) > 2(k+1)

2(2^k) > 2(k+1)

2^k > k+1 [B]

now if n = k is true, [2^k > 2k is true] then we have

"2^k > 2k and k+1"

and as A is true, we know that B is true, and if it holds for k+1 it holds for all values of k, and thus all values of n.

Personally i'm never sure how far to go with them, whether you're meant to continue on to prove that 2k is actually greater than (k+1) or not, i don't know..

Stubbsy
8. (Original post by Expression)
I don't doubt your solution, infact it looks quite cushy, but how did we get from

2^(n+1) = 2 * (2^n) (which I'm fine with) > 2* 2n
We have assumed that 2^n > 2n. Multiplying both sides by 2,

2 * (2^n) > 2 * (2n).
9. (Original post by Jonny W)
We have assumed that 2^n > 2n. Multiplying both sides by 2,

2 * (2^n) > 2 * (2n).

LOL. Nice little manipulation !

And:

(Original post by Jonny W)

= 4n = 2(n+1) + 2(n-1)
Is something that clearly works, but not something that (certainly I) would have thought of doing straight away !

Nice job.
10. (Original post by Jonny W)
I offer rep for the first person who proves by induction that there is an integer K such that, for all k >= K,

2^k > k^10.
2^k > k^10

Just some exploration:

Obviously when 1<k<10 at least, the expression is untrue:

2^2 > 2^10 ? no
2^10 > 10^10 ? no

For k < 1

2^(1/2) > (1/2)^10? yes
2^(1/3) > (1/3)^10? yes

But these are not integers. For negative values of k: -1 > k

2^(-2) > (-2)^10?

Because of the even index on the right hand side, the right hand side will always be positive. So will the left hand side, because negative index numbers do not give negative numbers. So we may simplify this, is the special case for negative integers, to:

1/(2^|k|) > |k|^10

But as k gets very large and negative, the LHS will tend to zero, and the RHS will tend to infinity. So the best hope we have of satisfying this is when k is the smallest negative number possible, and try k = -1, k = -2:

1/(2^|-1|) > |-1|^10
1/2 > 1 ? no.

1/(2^|-2|) > |-2|^10
1/4 > 1024? no

As we can see they will never meet in the middle, and the inequality will not be satisfied so long as k increases.

What about: 0 < k < -1? Well, they aren't integers, although from a short look there are some values which satisfy the inequality (I think).

So back to positive integers:

2^k > k^10

Taking logs,

k ln 2 > 10 ln k
k/(ln k) > 10/(ln 2)
k/(ln k) > 14.427 (5s.f.)

Try some values for k:

k = 10

10/(ln 10) > 14.427? no
20/(ln 20) > 14.427? no
50/(ln 50) > 14.427? no
80/(ln 80) > 14.427? yes... aha
65/(ln 65) > 14.427? yes
60/(ln 60) > 14.427? yes
55/(ln 55) > 14.427? no
56/(ln 56) > 14.427? no
57/(ln 57) > 14.427? no
58/(ln 58) > 14.427? no
59/(ln 59) > 14.427? yes

so the first integer value of k which satisfies the inequality is 59:

2^k > k^10
2^58 > 58^10 ? no
2^59 > 59^10 ? yes

So we have found K.

Now to prove that for all k >_ K, the inequality is satisfied, by induction:

We know it works with 59.

Now suppose it works for all values of k above 59:

2^(k+1) > (k+1)^10
2*2^k > k^10 + 10k^9 + 45k^8 + 120k^7 + 210k^6 + 252k^5 + 210k^4 + 120k^3 + 45k^2 + 10k + 1

Wait... wrong way (what a waste of time)

(k+1) ln 2 > 10 ln (k+1)
(k+1)/(ln (k+1)) > 10/(ln 2)

What now? I know it works for 59 and above, but can't prove this becuase I don't know how to use the fact it works for 59 and not below to finish...

Argh. Oh well.
11. (Original post by Jonny W)
I offer rep for the first person who proves by induction that there is an integer K such that, for all k >= K,

2^k > k^10.
Q. For which positive integers is it true that 2^k > k^10 ?

We have that for k=59, then 2^59 > 59^10 (thanks to mik1a)

Let P(k) be the statement that 2^k > k^10.

Having seen that P(59) is true, then the basis for induction is established.
The induction hypothesis is,

2^k > k^10, where k >59.

We now have to show that

2^(k+1) > (k+1)^10

Now 2^(k+1) = 2.2^k and so the induction hypothesis gives

2^(k+1) > 2.k^10

Therefore it suffices to show that for any k >=59,

2.k^10 >= (k+1)^10,

or rearranging,

(1+1/k)^10 <= 2

Consider the following argument. As k>1 the largest value of (1+1/k)^10 comes from the largest value of (1+1/k). This is turn comes from the smalles value of k, namely k=59. However (1+1/59)^10=1.183, which is less than 2. This completes the induction step.
Hence, by the Generalised Principle of Mathematical Induction, the proposition is true.

This is, more or less, a modification I took from my course notes (Number Theory) for a proof for 2^k > k³. And, as you can see, will apply to all powers of 2^k.
Now, this may make the giving of rep a bit dubious, since it wasn't actually me who did the proving. In consequence of which I must claim that I had already proved the proposition, albeit by a somewhat more tedious method!

I include the method from my notes as it's shorter and neater, But to claim my rep I submit my own proof

I'm going to give the proof for k=3 only, as a method from which proofs for higher powers can be generated. I's also easier to follow the arguments when the (k+1)^3 bracket is expanded than if it were (k+1)^10.
We have
2^k > k^3, k=10 (induction hypothesis)

Required to prove
2^(k+1) > (k+1)^3, k >= 10
or
2.2^k > (k+1)^3

now

2.2^k > 2.k^3 = k^3 + k^3, from the induction hypothesis

k³ > 10k², k>10
k³ > 6k²
k³ > 3k² + 3k²
=========

k² > 10k, k>10
3k² > 30k
=> k³ > 3k² + 30k
k³ > 3k² + 3k + 27k
=============

k > 10
27k > 270 > 1
=> k³ > 3k² + 3k + 1
=> 2k³ > k³ + 3k² + 3k + 1
=> 2k³ > (k+1)³
===========

which completes the inducion step.
Hence, by the Generalised Principle of Mathematical Induction, the proposition is true.
12. what board is this? its very similar to OCR p4
13. (Original post by jonas123)
what board is this? its very similar to OCR p4
Edexcel - straight from the most useless official textbook in the world

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: June 25, 2004
Today on TSR

### Edexcel GCSE Maths Unofficial Markscheme

Find out how you've done here

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams