The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

Proof by induction

Proving 7^n + 4^n +1 is divisible by 6, for all positive integers.

I obtain f(k+1)=f(k)+6(7^k)+3(4^k), assuming true for n=k, and having proved it true for n=1.

Am I alright to conclude f(k+1) as divisible by six as the minimum value of 4^k=4 and 4^k is always even?

Alternatively, is there a more elegant way to complete this?

Cheers.
Original post by fayled
Proving 7^n + 4^n +1 is divisible by 6, for all positive integers.


Am I alright to conclude f(k+1) as divisible by six as the minimum value of 4^k=4 and 4^k is always even?


I dont think that is valid.

Perhaps you should consider f(k+1) - f(k)
Reply 2
Avatar for fayled
fayled
OP
9
Original post by Phoebe Buffay
I dont think that is valid.

Perhaps you should consider f(k+1) - f(k)


Why is it not valid? n takes integer values from 1 upwards, and even x even = even, with 4 being even. Then even x 3 will give us a multiple of 6... And f(k+1)-f(k) wouldn't change the 3(4^k) term which is the only one I'm concerned about, so how would this help?
Original post by fayled
Why is it not valid? n takes integer values from 1 upwards, and even x even = even, with 4 being even. Then even x 3 will give us a multiple of 6... And f(k+1)-f(k) wouldn't change the 3(4^k) term which is the only one I'm concerned about, so how would this help?


Actually you are right. But look at what you wrote:


Original post by fayled
f(k+1)=f(k)+6(7^k)+3(4^k).


This is the same as considering f(k+1)-f(k)

If f(k) is divisible by 6, and f(k+1)-f(k) is divisible by 6, then so is f(k+1)
Reply 4
Avatar for fayled
fayled
OP
9
Original post by Phoebe Buffay
Actually you are right. But look at what you wrote:




This is the same as considering f(k+1)-f(k)

If f(k) is divisible by 6, and f(k+1)-f(k) is divisible by 6, then so is f(k+1)


Yes, I know that as long as 3(4^k) is divisible by 6, then it follows that f(k+1) is.

I don't really see how it matters whether you consider f(k+1)=... or f(k+1)-f(k)=..., as they both yield the same conclusion in this context.
Reply 5
Avatar for Blazy
Blazy
8
Original post by fayled
Proving 7^n + 4^n +1 is divisible by 6, for all positive integers.

I obtain f(k+1)=f(k)+6(7^k)+3(4^k), assuming true for n=k, and having proved it true for n=1.

Am I alright to conclude f(k+1) as divisible by six as the minimum value of 4^k=4 and 4^k is always even?

Alternatively, is there a more elegant way to complete this?

Cheers.


Not really more elegant but if you rewrite 6(7k)+3(4k)6(7^{k})+3(4^{k}) by factorising the 3 out, it will be a lot clearer.

Edit: Or even better, just factorise a 6 out straight away if you can...
(edited 10 years ago)
Original post by fayled
I don't really see how it matters whether you consider f(k+1)=... or f(k+1)-f(k)=..., as they both yield the same conclusion in this context.


Yes. As long as you get the relation between f(k+1) and f(k)
Reply 7
Avatar for pop101
pop101
10
Original post by fayled
Proving 7^n + 4^n +1 is divisible by 6, for all positive integers.

I obtain f(k+1)=f(k)+6(7^k)+3(4^k), assuming true for n=k, and having proved it true for n=1.
Am I alright to conclude f(k+1) as divisible by six as the minimum value of 4^k=4 and 4^k is always even?
Alternatively, is there a more elegant way to complete this?
Cheers.


f(k+1) - f(k) = 6(7^k) + 3(4^k)
= 6(7^k + 0.5(4^k))
Reply 8
Avatar for LogicGoat
LogicGoat
8
Original post by fayled
Proving 7^n + 4^n +1 is divisible by 6, for all positive integers.

I obtain f(k+1)=f(k)+6(7^k)+3(4^k), assuming true for n=k, and having proved it true for n=1.

Am I alright to conclude f(k+1) as divisible by six as the minimum value of 4^k=4 and 4^k is always even?

Alternatively, is there a more elegant way to complete this?

Cheers.


That's fine but you might find it more useful to write 3(4k)3(4^k) as 3(22k)3(2^{2k}) which is the same as 6(22k−1)6(2^{2k-1}) which is a bit more 'obviously' divisible by 6 since you don't need a wordy explanation.

Hope this was useful :smile:

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you