You are Here: Home >< Maths

# proof by induction help please watch

1. I always get stuck on the k+1 part

I have no idea what to do once I reach that stage, and this has cost me many marks in practise papers

2. We can't help unless you give us the question and show your working.
3. The idea is that you're told to prove that something is true for all n. You check the base case (usually n=0 or 1), and then you assume it's true for n=k. What you then have to do is, assuming no more than that it is true for n=k, follow a sequence of logical steps to show that, if it's true for n=k, then it's true for n=k+1.

For example say we have to show that for all . Clearly so the base case is fine. Next we assume that . Now, we can write . The first term is zero by our assumption that , and the second term is zero because we know that , and so assuming truth for n=k implies truth for n=k+1. That's the inductive step, so we're done.
4. A general hint for induction problems: You usually want to show . What you need to do is find a link between and . If it's a summation problem you will probably want to consider , if it's a product problem it might be and so on.
5. (Original post by nuodai)
The idea is that you're told to prove that something is true for all n. You check the base case (usually n=0 or 1), and then you assume it's true for n=k. What you then have to do is, assuming no more than that it is true for n=k, follow a sequence of logical steps to show that, if it's true for n=k, then it's true for n=k+1.

For example say we have to show that for all . Clearly so the base case is fine. Next we assume that . Now, we can write . The first term is zero by our assumption that , and the second term is zero because we know that , and so assuming truth for n=k implies truth for n=k+1. That's the inductive step, so we're done.
this is very confusing to me :/, just the k+1 part.
6. http://i.imgur.com/h2ahK.png

for example here, i know on the right side he just replaced k with k+1, but on the left side why does he turn (3k-4) into (3k-4) + (3(k+1)-4)

are you meant to leave the (3k-4) in the lhs THEN add another value that is with the k's replaced with k+1?

thanks
7. (Original post by TimetoSucceed)
http://i.imgur.com/h2ahK.png

for example here, i know on the right side he just replaced k with k+1, but on the left side why does he turn (3k-4) into (3k-4) + (3(k+1)-4)

are you meant to leave the (3k-4) in the lhs THEN add another value that is with the k's replaced with k+1?

thanks
You're trying to show that, for all n, . Now, the LHS in the case n=k looks like:

The goal is to show that the n=k+1 sum is equal to what you get when you replace 'n' by 'k+1' in the formula for what you're trying to show. The LHS in the case n=k+1 looks like:

But inside the is hidden a load of other terms, and is one of them (it's just the kth term in the sum), because to get to the n=k+1 sum you add the (k+1)th term to the n=k sum, right? And so to emphasise what you're meant to do, it's been written as

What he's put on the RHS is what you need to try to show is true, using only your assumption about the n=k case. Your assumption about the n=k case tells you that

and so you can write your n=k+1 sum as:

(Because to get from the n=k sum to the n=k+1 sum you just add the (k+1)th term to both sides)

You then have to rearrange this to show that it's equal to .

I've tried to make this as clear and obvious as I can, but if you still don't understand, let me know (but refer to specific parts rather than 'the k+1 bit').

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: April 12, 2011
Today on TSR

### Are exams rubbish?

Is the exam system out of date?

### University open days

• University of Exeter
Wed, 24 Oct '18
Wed, 24 Oct '18
• Northumbria University
Wed, 24 Oct '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