# Proof by induction [Sorry!!!]Watch

#1
Okay, I've found out there are several different types of questions for FP1 where you are asked to prove something using induction.

There's the series one, the sequences one, the matrix one [which I yet have to learn] and the divisibility one.

However, I'm stuck on the divisibility one i.e. the one where you have f(n).
The book I'm using states that these questions are tackled by simplifying " f(k+1) - f(k) " OR " f(k+1) + f(k) ".

Now my question is, how do you know which one of these to use???

Thanks! [Examples would be nice ]
0
9 years ago
#2
(Original post by Narik)
The book I'm using states that these questions are tackled by simplifying " f(k+1) - f(k) " OR " f(k+1) + f(k) ".

Now my question is, how do you know which one of these to use???
Either method is valid, the dilemma is which will work best for a particular question.

I would think that, playing the odds, you'd be best off simplifying f(k+1) - f(k) unless there's something particularly tempting about the other approach.

In fact, can you actually give an example where they say you should simplify f(k+1)+f(k)?
0
#3
(Original post by DFranklin)
Either method is valid, the dilemma is which will work best for a particular question.

I would think that, playing the odds, you'd be best off simplifying f(k+1) - f(k) unless there's something particularly tempting about the other approach.

In fact, can you actually give an example where they say you should simplify f(k+1)+f(k)?
Thanks and here is the example.

Prove that: 2^(3n + 2) + 5^(n + 1) is divisible by 3

The working out uses f(k+1) + f(k) and I tried it using f(k+1) - f(k) but it didn't work...

http://www.schoolworkout.co.uk/.../r...0induction.doc

[On page 8]
0
9 years ago
#4
Using f(k+1)-f(k) seems to work fine to me :

Spoiler:
Show
f(k+1)-f(k) = 2^(3n+2)(2^3 - 1) + 5^(n+1)(5-1) = 7(2^(3n+2))+4(5^(n+1)) = 6(2^(3n+2))+3(5^(n+1)) + (2^(3n+2)+5^(n+1)).

The first 2 terms are obviously divisible by 3 and the last term is f(k) and so is divisible by 3 by induction. Then since f(k+1)-f(k) and f(k) are both divisible by 3, so is f(k+1).

[N.B. your link doesn't seem to work so I can't compare whether it was much easier using f(k+1)+f(k)].
0
#5
(Original post by DFranklin)
Using f(k+1)-f(k) seems to work fine to me :

Spoiler:
Show
f(k+1)-f(k) = 2^(3n+2)(2^3 - 1) + 5^(n+1)(5-1) = 7(2^(3n+2))+4(5^(n+1)) = 6(2^(3n+2))+3(5^(n+1)) + (2^(3n+2)+5^(n+1)).

The first 2 terms are obviously divisible by 3 and the last term is f(k) and so is divisible by 3 by induction. Then since f(k+1)-f(k) and f(k) are both divisible by 3, so is f(k+1).

[N.B. your link doesn't seem to work so I can't compare whether it was much easier using f(k+1)+f(k)].
So basically, it doesn't matter which you use, although one method may be simpler than the other, as both will give you the end result. Thank you so much!!
0
X

new posts
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• Cranfield University
Cranfield Forensic MSc Programme Open Day Postgraduate
Thu, 25 Apr '19
• University of the Arts London
Open day: MA Footwear and MA Fashion Artefact Postgraduate
Thu, 25 Apr '19
• Cardiff Metropolitan University
Sat, 27 Apr '19

### Poll

Join the discussion

#### Have you registered to vote?

Yes! (228)
39.31%
No - but I will (40)
6.9%
No - I don't want to (41)
7.07%
No - I can't vote (<18, not in UK, etc) (271)
46.72%