Proof by induction [Sorry!!!] Watch

Narik
Badges: 13
Rep:
?
#1
Report Thread starter 9 years ago
#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
reply
DFranklin
Badges: 18
Rep:
?
#2
Report 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
reply
Narik
Badges: 13
Rep:
?
#3
Report Thread starter 9 years ago
#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...

Here is the link:

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

[On page 8]
0
reply
DFranklin
Badges: 18
Rep:
?
#4
Report 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
reply
Narik
Badges: 13
Rep:
?
#5
Report Thread starter 9 years ago
#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!! :thanks:
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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
    Undergraduate Open Day - Llandaff Campus Undergraduate
    Sat, 27 Apr '19

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%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise