You are Here: Home

# FP1, Divisibility Proof by Induction

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
1. FP1, Divisibility Proof by Induction
It's just these questions that are holding me back and I'm really frustrated. I know you must first do f(1) , then f(k), then f(k+1).

However, on the inductive step, how do you know whether to do:

f(k+1) - f(k)
f(k+1) + f(k)
f(k+1) +/- N f(k) where N is some integer

And after this step, what kind of manipulation do you do? I cant find a "target" if you know what I mean - like when proving a summation formula your "target" is the summation they give, but replace (n) by (k + 1).

This question for example:

Prove that is exactly divisible by 4 for all integers of n.

So which is divisible by 4.

Assume that this is divisible by 4.

And then after simplifying f(k+1) you get

If i'm not mistaken, you can do f(k+1)+f(k) for this particular question and it will work.

But is it trial and improvement or some other method you use you determine this?
2. Re: FP1, Divisibility Proof by Induction
(Original post by bong)
It's just these questions that are holding me back and I'm really frustrated. I know you must first do f(1) , then f(k), then f(k+1).

However, on the inductive step, how do you know whether to do:

f(k+1) - f(k)
f(k+1) + f(k)
f(k+1) +/- N f(k) where N is some integer

And after this step, what kind of manipulation do you do? I cant find a "target" if you know what I mean - like when proving a summation formula your "target" is the summation they give, but replace (n) by (k + 1).

This question for example:

Prove that is exactly divisible by 4 for all integers of n.

So which is divisible by 4.

Assume that this is divisible by 4.

And then after simplifying f(k+1) you get

If i'm not mistaken, you can do f(k+1)+f(k) for this particular question and it will work.

But is it trial and improvement or some other method you use you determine this?
f(k+1) - f(k) also works but it's a bit messier.

I don't think there's a 'way' to do it. You just have to practice at it and then you'll get used to spotting what to do.
3. Re: FP1, Divisibility Proof by Induction
(Original post by hassi94)
f(k+1) - f(k) also works but it's a bit messier.

I don't think there's a 'way' to do it. You just have to practice at it and then you'll get used to spotting what to do.
Thanks but i'm still not able to do the dodgy ones where you need a add/subtract a multiple of f(k) from f(k+1). When I see the mark schemes it just seems completely random and I think how the hell am I supposed to see that.
4. Re: FP1, Divisibility Proof by Induction
(Original post by bong)
Thanks but i'm still not able to do the dodgy ones where you need a add/subtract a multiple of f(k) from f(k+1). When I see the mark schemes it just seems completely random and I think how the hell am I supposed to see that.
With those ones they're usually set up to be a bit easier. Can you post an example so I can have a look?
5. Re: FP1, Divisibility Proof by Induction
(Original post by hassi94)
With those ones they're usually set up to be a bit easier. Can you post an example so I can have a look?
Prove that is divisible by 11
6. Re: FP1, Divisibility Proof by Induction
(Original post by bong)
Prove that is divisible by 11
Ok, here's how I'd do this question with adding multiples.

Because you know you'll have to sub in n = k+1 at some point, (i.e. ) when you get to the stage where you say, assume true for n = k:

You think - how do I connect the two: You may notice that is 16 times bigger than - sounds like an idea, so let's multiply the whole thing by 16:

Now for n = k+1:

This looks fairly similar to 176m - but is a bit of a bother. Try factorising it.

This looks a lot better - we have and .

This looks pretty good - we can factor out 11, and hence, complete the induction - so if it's true for n = k, then it is true for n = k+1...blah blah blah.
7. Re: FP1, Divisibility Proof by Induction
(Original post by Blazy)
...
Cheers for that - I've come across that method where you equate it to an integer 'm' and carry on like you did, but I was't taught this way. Perhaps I'll learn it, exams on Friday so there's some time.

Thanks

## Step 2: Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank

this is what you'll be called on TSR

2. this can't be left blank

never shared and never spammed

3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
1. By completing the slider below you agree to The Student Room's terms & conditions and site rules

2. Slide the button to the right to create your account

You don't slide that way? No problem.

Last updated: May 30, 2012
Study resources