The Student Room Group

Proof by induction

f(n)=2n+6nf(n)=2^n +6^n


show thatf(k+1)=6f(k)4(2k)show\ that f(k+1)=6f(k)-4(2^k)


prove by induction that f(n) is divisible by 8


I managed to do the show that bit and this is how far i've gotten to

Assume that f(k)=2^k +6^k is divisible by 8 and i don't know how to rearrange the bit which i showed to get 2k+1+6k+12^{k+1} +6^{k+1}

Scroll to see replies

Reply 1
Original post by huiop
f(n)=2n+6nf(n)=2^n +6^n


show thatf(k+1)=6f(k)4(2k)show\ that f(k+1)=6f(k)-4(2^k)


prove by induction that f(n) is divisible by 8


I managed to do the show that bit and this is how far i've gotten to

Assume that f(k)=2^k +6^k is divisible by 8 and i don't know how to rearrange the bit which i showed to get 2k+1+6k+12^{k+1} +6^{k+1}


All you need to do is prove for the n = 1 case, then you assume that it is true for f(k) for some k. Now that you have shown the relationship between f(k+1) and f(k), all you need to do is notice that 6f(k) is divisible by 8 and so is 4(2k) 4(2^{k}) . This is because it can be written as 8(2k1) 8(2^{k-1})

Hope this helps.
(edited 7 years ago)
Reply 2
Original post by AMarques
All you need to do is prove for the n = 1 case, then you assume that it is true for f(k) for some k. Now that you have shown the relationship between f(k+1) and f(k), all you need to do is notice that 6f(k) is divisible by 8, and so is 4(2k) 4(2^{k}) . This is because it can be written as 8(2k1) 8(2^{k-1})

Hope this helps.


could you show me the steps into how this works?
Reply 3
Original post by huiop
could you show me the steps into how this works?


Assuming you want me to clarify the last line, notice that 4(2k) 4(2^{k}) can be written as 422k1 4\cdot 2\cdot 2^{k-1} If we multiply the 4 and 2 we get 8. We assumed f(k) was divisible by 8, and so 6f(k) is divisible by 8, and so is the last term, i.e we can then say that all the terms in f(k+1) are divisible by 8, so f(k+1) must be divisible by 8, assuming f(k) is divisible by 8.

Not sure how to make it more clear, and I don't want to write the whole working out, you should try it for yourself.
Reply 4
Original post by AMarques
Assuming you want me to clarify the last line, notice that 4(2k) 4(2^{k}) can be written as 422k1 4\cdot 2\cdot 2^{k-1} If we multiply the 4 and 2 we get 8. We assumed f(k) was divisible by 8, and so 6f(k) is divisible by 8, and so is the last term, i.e we can then say that all the terms in f(k+1) are divisible by 8, so f(k+1) must be divisible by 8, assuming f(k) is divisible by 8.

Not sure how to make it more clear, and I don't want to write the whole working out, you should try it for yourself.


i understand how to do the logic bit(even though i might not express it in the clearest of ways) i don't understand though how 4(2k)4×2(2k1)4(2^k) \Rightarrow 4\times 2(2^{k-1}) i don't quite see how taking a factor of 2 out turns the 2^k to a 2^k-1
Original post by huiop
i understand how to do the logic bit(even though i might not express it in the clearest of ways) i don't understand though how 4(2k)4×2(2k1)4(2^k) \Rightarrow 4\times 2(2^{k-1}) i don't quite see how taking a factor of 2 out turns the 2^k to a 2^k-1


Quite simply: 2k=22k1=2(2k21)=22k22^k=2\cdot 2^{k-1}=2\cdot (2^k \cdot 2^{-1})=2\cdot \frac{2^k}{2}
Reply 6
Original post by RDKGames
Quite simply: 2k=22k1=2(2k21)=22k22^k=2\cdot 2^{k-1}=2\cdot (2^k \cdot 2^{-1})=2\cdot \frac{2^k}{2}


oh thanks, i've never seen something done this way before.

Thanks so much ^-^
Original post by huiop
oh thanks, i've never seen something done this way before.

Thanks so much ^-^


It's basic index laws which you should have studied in C1. Unfortunately many students these days, not just you, seem to gloss over them, but as a result I strongly suggest that you go back and take the opportunity to review your rules of indices and logarithms, as well as your basic algebra.
Reply 8
Original post by huiop
oh thanks, i've never seen something done this way before.

Thanks so much ^-^


Seriously? Have you not done C1 before?
Original post by Zacken
Seriously? Have you not done C1 before?


U savage


Posted from TSR Mobile
Reply 10
Original post by HapaxOromenon3
It's basic index laws which you should have studied in C1. Unfortunately many students these days, not just you, seem to gloss over them, but as a result I strongly suggest that you go back and take the opportunity to review your rules of indices and logarithms, as well as your basic algebra.


Original post by Zacken
Seriously? Have you not done C1 before?


Original post by physicsmaths


To be perfectly honest, the rule quoted is nothing more than GCSE indices knowledge. It's not so much C1 knowledge that lets people down, it's a failure to have a good grasp of the basics when they finish GCSE.
Reply 11
Original post by Zacken
Seriously? Have you not done C1 before?

i have....
Original post by HapaxOromenon3
It's basic index laws which you should have studied in C1. Unfortunately many students these days, not just you, seem to gloss over them, but as a result I strongly suggest that you go back and take the opportunity to review your rules of indices and logarithms, as well as your basic algebra.


Hmm i understand the way it works now i never saw something done this way :/

so surely if the term 6f(k)is divisible by 8 thats fine so surely the term 4(2k)the\ term\ 6f(k) is\ divisible\ by\ 8\ that's\ fine\ so\ surely\ the\ term\ 4(2^k) is also divisible by 8 then? But why do i have to make it have a 8 in front to show that it's divisible by 8?

or
do i only know that the term 4(2k)4(2^k) is divisible by 8 after i rearrange the term to have an 8 in front?

or am i speaking bs?
(edited 7 years ago)
Reply 12
Original post by huiop
i have....


lol.


Hmm i understand the way it works now i never saw something done this way :/

so surely if the term 6f(k)is divisible by 8 thats fine so surely the term 4(2k)the\ term\ 6f(k) is\ divisible\ by\ 8\ that's\ fine\ so\ surely\ the\ term\ 4(2^k) is also divisible by 8 then? But why do i have to make it have a 8 in front to show that it's divisible by 8?

or
do i only know that the term 4(2k)4(2^k) is divisible by 8 after i rearrange the term to have an 8 in front?

or am i speaking bs?


Essentially you have 4 * (even number), so that's always divisible by 8 since it will always have a factor of 8 in it, to make that clear to the reader, you put it in the form 8g(k) so that the factor of 8 is apparent.
Reply 13
Original post by huiop
i have....


Hmm i understand the way it works now i never saw something done this way :/

so surely if the term 6f(k)is divisible by 8 thats fine so surely the term 4(2k)the\ term\ 6f(k) is\ divisible\ by\ 8\ that's\ fine\ so\ surely\ the\ term\ 4(2^k) is also divisible by 8 then? But why do i have to make it have a 8 in front to show that it's divisible by 8?

or
do i only know that the term 4(2k)4(2^k) is divisible by 8 after i rearrange the term to have an 8 in front?

or am i speaking bs?


k2+k (kZ) k^2+k \ (k\in \mathbb{Z}) is always divisible by 2 but doesn't have a 2 out that can be taken out as a factor seemingly.
Original post by B_9710
k2+k (kZ) k^2+k \ (k\in \mathbb{Z}) is always divisible by 2 but doesn't have a 2 out that can be taken out as a factor seemingly.


k2+k=k(k+1)k^2 + k = k(k+1). For any integer kk, exactly one of kk and k+1k+1 is divisible by 2.
Reply 15
Original post by marioman
k2+k=k(k+1)k^2 + k = k(k+1). For any integer kk, exactly one of kk and k+1k+1 is divisible by 2.


Yeah, why have you told me this?
Original post by B_9710
Yeah, why have you told me this?


It can be divisible by 2 whilst not having a 2 that can be taken out as a factor.
Reply 17
Original post by marioman
It can be divisible by 2 whilst not having a 2 that can be taken out as a factor.


I know I already said that. What's your point though?
Original post by B_9710
I know I already said that. What's your point though?


The way you worded your post suggested that you didn't understand how it could be divisible by 2 whilst not having a 2 that can be taken out as a factor.
Original post by marioman
It can be divisible by 2 whilst not having a 2 that can be taken out as a factor.


Lol you have literally just repeated everything he said.



Posted from TSR Mobile

Quick Reply