You are Here: Home >< Maths

# Induction - say wha'?! watch

1. (Original post by Simplicity)
Obviously, he knows the principle of it.
I'd have said it was pretty obvious he didn't.

(Original post by Simplicity)
But, then you have to build up intuition by working it out yourself.
Aren't you the person who keeps going on about how no one should have to practise maths? [/*****y]
2. (Original post by generalebriety)
I'd have said it was pretty obvious he didn't.
I guess so. I think his only mistake is he thinks you have to with n=k+1 which is wrong. I guess you could have said go back to the post with the ladder analogy.

(Original post by generalebriety)
Aren't you the person who keeps going on about how no one should have to practise maths? [/*****y]
I have know changed my mind. You should practice alot and have only basic help i.e. no big hints.

P.S. Although, its pretty hard when you don't have big hints for stuff.
3. So by multiplying both sides by (1+x) we have k+1 on both sides, yes?

So

wouldn't (1+x)^k be a binomial expansion, but how to expand?
4. (Original post by mcp2)
So by multiplying both sides by (1+x) we have k+1 on both sides, yes?

So

wouldn't (1+x)^k be a binomial expansion, but how to expand?
Why do you need to expand it?

I think you're misunderstanding quite how induction works...
5. That is exactly the problem here, I don't quite understand induction. I know that if something works for all real integers then we should be able to prove that by replacing k by k+1, right? My other problem is that I don't know what the end result should look like. I mean, what's above in my previous post, is that correct?

I'm going to go think about it more and will be back tomorrow. Night homeboys.
6. (Original post by mcp2)
That is exactly the problem here, I don't quite understand induction. I know that if something works for all real integers then we should be able to prove that by replacing k by k+1, right? My other problem is that I don't know what the end result should look like. I mean, what's above in my previous post, is that correct?

I'm going to go think about it more and will be back tomorrow. Night homeboys.
Suppose we have a sentence about a positive integer n, and we want to know which n it's true for. If we know it's true for n = 1, and we can show that truth for n = k implies truth for n = k+1, then we know it's true for all positive integers. Can you see why? (Because truth for n = 1 implies truth for n = 2, but then truth for n = 2 implies truth for n = 3, and so on...)

So let's start off. We've proven that your inequality is true for n = 1. Now we assume it's true for n = k, and try to prove from there that it's true for n = k+1. The statement for n = k is "(1 + x)^k >= 1 + kx", which we assume true. We want to prove "(1 + x)^(k+1) >= 1 + (k+1)x" from there, and the obvious way to do it is to take (1 + x)^k = 1 + kx and then multiply both sides by (1 + x).
7. I see. Seeing as how at this level I am already given the proof for n=k so the next logical step would be to prove it true for n=k+1 either by addition or multiplication or replacement, etc, yes?

Does it matter if the final form of the proof doesn't look anything like the original?
8. (Original post by mcp2)
I see. Seeing as how at this level I am already given the proof for n=k so the next logical step would be to prove it true for n=k+1 either by addition or multiplication or replacement, etc, yes?

Does it matter if the final form of the proof doesn't look anything like the original?
(Original post by mcp2)
That is exactly the problem here, I don't quite understand induction. I know that if something works for all real integers then we should be able to prove that by replacing k by k+1, right? My other problem is that I don't know what the end result should look like. I mean, what's above in my previous post, is that correct?

I'm going to go think about it more and will be back tomorrow. Night homeboys.
You do not seperately prove anything for n=k and n=k+1. Also, "proof by replacement" doesn't work in this case, because we have specifically only assumed something to be true for n=k. We do not yet know whether it is true for n=k+1. Indeed, that's exactly what we're trying to show (using the fact that something is true for n=k).

The idea is to show that if

is true, then

is also true. The thing you're being asked to do is show a logical implication: if A is true then B is true.

If we can do this, and we know that it is true for k=1, can you see why that would imply that it is also true for k=2 and k=3 etc. for all integer k's?

Try substituting in k=1. Just plugging in, it's clear that if

is true we also now know that

or, in other words, that

So it's also true for k=2. That means we can substitute in k=2 into the first equation again, and that shows that it is true for k=3. How? Well, if

is true, then

is true.

Substituting k=3 implies k=4 and so on.

This is exactly why GE suggested you multiply by . Because

So by multiplying by we can get the left hand side of the equation from an expression with k to an expression with k+1. This is how we show the logical implication. By manipulating and playing around with the original expression until we reach what we want.

Continuing the inductive argument,

If we multiply the whole inequality by , firstly it remains an inequality, which is important, because we want our end result to still be an inequality. Secondly, we've got from our expression with k to an expression with (k+1) which is what we were trying to do.

So

Now is a square, and is therefore always positive. So if we add something positive onto a quantity, it will only increase, so:

then clearly

When I originally read your post, I almost got the impression that you had the process and the end result mixed up. The process is going from k to k+1, and the end result is the thing with k+1. It should look exactly the same, but with k+1's in the place of k's.

If you want another classic example, ladders are one, dominoes are another.

You want to prove that, for all integers , if you set up a chain of n dominoes, all n dominoes fall down.

You assume that this is true for some number k, i.e. if you set up a chain of k dominoes, all k will fall down. Now this obviously includes the kth domino, so if you add another domino onto the end, a k+1th domino, because you know the kth domino will topple, and because you've set up the k+1th domino in such a way that toppling one will topple the other, you can conclude that a chain of k+1 dominoes will also necessarily result in k+1 dominoes falling down.

This is showing the implication. Showing A leads to B. Showing that if the statement is true for k, it is also true for k+1.

But you still have no concrete evidence. You only know that if you can set up a number of dominoes so that they all fall, then if you add one onto the chain, they will still all fall.

So you set up one domino, and watch it fall. You've just shown that your hypothesis is true for n=1. This is the base case. This allows you to use your implication to prove your hypothesis for all natural numbers. You know that if you add another domino to your single domino, both will fall. And adding another will result in all three falling. Since this extends through all the natural numbers, you've proved what you wanted to.

I hope this helps.
9. (Original post by mcp2)
That is exactly the problem here, I don't quite understand induction. I know that if something works for all real integers then we should be able to prove that by replacing k by k+1, right? My other problem is that I don't know what the end result should look like. I mean, what's above in my previous post, is that correct?

I'm going to go think about it more and will be back tomorrow. Night homeboys.
Did you read my post?... I'm curious to know if it was helpful at all I'm finding the onslaught of examples quite overwhelming, so I'm not sure how helpful it will be for you to clutter your mind up with them before you understand the underlying notions. It might be better to put them out of your mind for a short while, think about how proof by induction works in theory, and then revisit all these examples and see how they fit into that context?
10. Yes it did help and I've started the examples in my book but still nothing is coming out as it should, induction, the bane of my life. I'm still in need of reading.
11. (Original post by mcp2)
I see. Seeing as how at this level I am already given the proof for n=k so the next logical step would be to prove it true for n=k+1 either by addition or multiplication or replacement, etc, yes?

Does it matter if the final form of the proof doesn't look anything like the original?
This seems a lot more difficult to get across than I had initially imagined. It's quite a subtle concept, but at no point have I "proven" it for n = k, I have said "what would happen if it was true for n = k?" and tried to deduce "ah, well then it must be true for n = k+1 too" from there. I put those words in bold in one of my previous posts too, to ensure you wouldn't attempt to prove n = k+1 separately from n = k.

Perhaps induction is a harder concept than I think to get your head around. But the ladder analogy given earlier in the thread is a good one. You know two sentences to be true: "I can get onto the 1st rung", and "if I can get onto the kth rung, then I can get onto the (k+1)th rung". Do you accept that this means you can climb onto the nth rung, for any n? Or Elongar's domino analogy - if "I can knock over the first domino" and "if the kth domino falls, the (k+1)th domino will fall", do you accept that you can make n dominoes fall down for any n?

The important thing to remember here is that n is a variable, and is used to point to a positive integer; k is fixed. We know by assumption (we don't prove it) that a certain statement (formula, inequality...) is true for n = k, and (if you like) n = k-1, k-2, ..., 2, 1. We don't know that it's true for n = k+1 (it might not be!), because k is fixed, and not variable. We want to prove from what we already know that it's true for n = k+1.

Read Elongar's post with this in mind, and tell us if there's anything you're still struggling with.
12. This might sounds a bit consescending (sorry ), but if you're not doing this already, writing everything down and following everything in clear, defined stages might help you get into the swing of it. Sometimes taking an overly methodical approach can help you find your way through something without trying to remember everything at once.

If you are still confused by the core idea, try clearing your mind of all the preconceptions you have so far, and try reading through a very clear explanation or example very carefully, checking that you understand what each bit means, and then how it all fits together. The dominoes analogy is nice at helping understand the overall picture.

I am not sure if it is wise to re-state this in a different way, but it might help. If you don't like this way of looking at it, then forget all about it It might just be that you need to find the a way of thinking about things that suits you best.
Suppose you have some equation that might or might not hold for all natural numbers .
(So you could take to indicate any of the statements that have been involved in the various examples - Elongar's example is probably a good starting point. But think of less specifically for now, if you want.)
Would you agree that if,
(i) is true
and
(ii) for all
then has to hold for all natural ?

In terms of dominoes, this is equivalent to
(i')We can make domino fall
and
(ii')if the domino falls, then the domino falls.
and like generalebriety said, this means that all the dominoes will eventually fall down.

Just think like this show
n=1 is correct or n=a.

Start from n=k, do some manipulation and ta dah k+1 replaces k.

P.S. Lack of reasoning skills or maybe not familar with the techniques like algebraic manipulation is the only reason for not getting induction.
14. Guys I think you'll be happy to hear that I understand induction now, lols. I also want to say that I was trying induction on summation of series when I had skipped that chapter (silly me). I'm sure my logic isn't poor.

So my new problem ist he second line of this, where did n(n+1) go?

15. (Original post by mcp2)
Guys I think you'll be happy to hear that I understand induction now, lols. I also want to say that I was trying induction on summation of series when I had skipped that chapter (silly me). I'm sure my logic isn't poor.

So my new problem ist he second line of this, where did n(n+1) go?

Factorise the n(n+1) from first line.
16. Ah OK thanks.

### 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: July 26, 2009
Today on TSR

### A-Level OCR Biology Unofficial Markscheme

Find out how you've done here

### 2,905

students online now

Exam discussions

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