You are Here: Home >< Maths

# Hard induction or am i being thick...? watch

1. ..
2. (Original post by thomas575)
Sorry tried to write in latex but wouldn't let me, error apparently....
it is to prove by induction the sum of 1/k from 1 to 2^(n-1) is greater than or equal to (n+1)/2

i was told to write down the sums for n=1,2,3,4,5
so....for
n=1: 1/1
n=2: 1/1+1/2
n=3: 1/1+1/2+1/3+1/4
n=4: 1/1+1/2+1/3+...+1/8
n=5: 1/1+1/2+1/3+................+1/16
Obviosuly i can see each time there is double the amount of fractions but cannot see how this is going to help me prove the above.
With induction, you do the following:

1) Show rule to be true for base case, n = 1.
2) Assume the rule holds for n = k.
3) Using 2), prove that the rule holds for n = k+1.

Can you do it using this procedure?
3. (Original post by Phugoid)
With induction, you do the following:

1) Show rule to be true for base case, n = 1.
2) Assume the rule holds for n = k.
3) Using 2), prove that the rule holds for n = k+1.

Can you do it using this procedure?
sorry should have mentioned. I know the procedure for induction, but it's that inductive step i can't seem to figure out where to start showing that it holds for k+1 once i've assumed that P(k) is true
4. (Original post by thomas575)
Sorry tried to write in latex but wouldn't let me, error apparently....
it is to prove by induction the sum of 1/k from 1 to 2^(n-1) is greater than or equal to (n+1)/2

i was told to write down the sums for n=1,2,3,4,5
so....for
n=1: 1/1
n=2: 1/1+1/2
n=3: 1/1+1/2+1/3+1/4
n=4: 1/1+1/2+1/3+...+1/8
n=5: 1/1+1/2+1/3+................+1/16
Obviosuly i can see each time there is double the amount of fractions but cannot see how this is going to help me prove the above.
Re-write the above statement as a summation.

So,

Now you want to show this holds for n+1. So add on the extra term, and then assume the above statement P(n) is true.
5. (Original post by Mathematician!)
Re-write the above statement as a summation.

So,

Now you want to show this holds for n= m+1. So add on the extra term, and then assume the above statement P(n) is true.
will it make alot of difference that it's an inequality though?
6. (Original post by thomas575)
will it make alot of difference that it's an inequality though?
Sorry, forgot to write it as the inequality. But it makes no difference to just use the equality statement (greater than or equal to is the same as = or >, and proving just one of these statements should be sufficient.)
7. (Original post by Mathematician!)
Sorry, forgot to write it as the inequality. But it makes no difference to just use the equality statement (greater than or equal to is the same as = or >, and proving just one of these statements should be sufficient.)
Also sorry i know i'm being a complete nuisance....!
The next term will not just be 1 term though because of the upper limit in the sigma notation is 2^n-1 not n. So as shown by writing down the sums it will be well i don't know how many more terms, can't seem to think atm. So how would i write this...?
8. (Original post by thomas575)
Also sorry i know i'm being a complete nuisance....!
The next term will not just be 1 term though because of the upper limit in the sigma notation is 2^n-1 not n. So as shown by writing down the sums it will be well i don't know how many more terms, can't seem to think atm. So how would i write this...?
It's 2^(n-1) to get it into the set of integers (I think).
Anyway, you need to add on the extra term 1/2^n to the summation during the inductive step.
9. When you go from n to n+1, how many extra terms are there in the sum?
And what is the smallest extra term?
Then the sum of the extra terms >= "number of extra terms" x "smallest extra term"
10. (Original post by DFranklin)
When you go from n to n+1, how many extra terms are there in the sum?
And what is the smallest extra term?
Then the sum of the extra terms >= "number of extra terms" x "smallest extra term"
Thanks, think this may get me there (i really hope so, sick of this lol). is it fair to say then that for the sum as above from 1 to 2^n then, when i do the inductive step i should get that it is greater than or equal to ((n+1)+1)/2=(n+2)/2?
11. (Original post by thomas575)
Thanks, think this may get me there (i really hope so, sick of this lol). is it fair to say then that for the sum as above from 1 to 2^n then, when i do the inductive step i should get that it is greater than or equal to ((n+1)+1)/2=(n+2)/2?
Yes, this is what you are trying to show (i.e. it is the end result).

### 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: January 23, 2010
Today on TSR

How do you think you'll do?

### University open days

Wed, 25 Jul '18
2. University of Buckingham
Wed, 25 Jul '18
3. Bournemouth University
Wed, 1 Aug '18
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