induction q's (1 Viewer)

[pillar]

Just got some induction questions. I'm pretty new to it and I've got a couple that I have a feeling may be wrong, but I can't really check as the textbook doesn't have answers and my teacher is away lol..

Prove for all n >= 1

5^n + 2x11^n is a multiple of 3

Working:

Try n = 1
5^1 + 2x11^1 = 27
27 = 3x9
hence is true for n = 1

Assume true for n = k
i.e. 5^k + 2x11^k = 3M (where M is an integer)
If true for n = k, then prove for n = k + 1
i.e. RTP 5^k+1 + 2x11^k+1 = 3P (where P is an integer)

Proof:
LHS = 5^k+1 + 2x11^k+1
= 5(5^k) + 2x11(11^k)
=5(5^k +2x11^k - 2x11^k) + 2x11(11^k)
=5(3M - 2x11^k) + 2x11(11^k) (since assumed for n = k)
=15M -10(11^k) + 22(11^k)
=15M + 12(11^k)
=3(5M + 4(11^k)
=3P (P = 5M + 4(11^k))




So I think that's right but I may have fucked up somewhere, or done something I'm not allowed to do or whatever.. either way if someone could have a look through that and see if that looks correct that'd be sweet

I also have another one I'll try to get up with Latex in a sec

cheers

 

[jet]

Yeah, that's good. But, you need to say that P is an integer, since both M and k are integers. Otherwise, it is not a multiple of 3.

 

[pillar]

Where exactly do I have to state that? Because I've already got it at

i.e. RTP 5^k+1 + 2x11^k+1 = 3P (where P is an integer)

Where else do I need to state it?

Thanks for your help

 

[jet]

=3(5M + 4(11^k)
=3P (where P is an integer since M and k are integers)

While you did assert that you had to prove the statement you quoted, with P as an integer, you need to show that the expression for P that you end up with is an integer as well, for your induction to work.

 

[pillar]

Ah okay I get it, thanks heaps.

 

[pillar]

Alright I got another one.. it's an inequality induction and I'm not sure if I've structured/worded the proof correctly.


Prove by induction 12^n > 7^n + 5^n, for n >= 2

Try n = 2
LHS = 12^2 = 144
RHS = 7^2 + 5^2 = 74
hence true for n = 2

Assume true for n = k
i.e. 12^k > 7^k + 5^k
If true for n = k, prove for n = k+1
i.e. RTP 12^k+1 > 7^k+1 + 5^k+1

Proof:
LHS = 12(12^k)
12(12^k) > 12(7^k + 5^k) (since assumed true for n = k)
12(12^k) > 12(7^k) + 12(5^k)
RHS = 7^k+1 + 5^k+1
= 7(7^k) + 5(5^k)
12(7^k) + 12(5^k) > 7(7^k) + 5(5^k) (since n >= 2)
.'. LHS > RHS

 

[Trebla]

Alright I got another one.. it's an inequality induction and I'm not sure if I've structured/worded the proof correctly.


Prove by induction 12^n > 7^n + 5^n, for n >= 2

Try n = 2
LHS = 12^2 = 144
RHS = 7^2 + 5^2 = 74
hence true for n = 2

Assume true for n = k
i.e. 12^k > 7^k + 5^k
If true for n = k, prove for n = k+1
i.e. RTP 12^k+1 > 7^k+1 + 5^k+1

Proof:
LHS = 12(12^k)
12(12^k) > 12(7^k + 5^k) (since assumed true for n = k)
12(12^k) > 12(7^k) + 12(5^k)
RHS = 7^k+1 + 5^k+1
= 7(7^k) + 5(5^k)
12(7^k) + 12(5^k) > 7(7^k) + 5(5^k) (since n >= 2)
.'. LHS > RHS

It would be more convincing if you went from LHS all the way to the RHS. The statement made here isn't very convincing because you haven't listed the reason that it holds. It needs to be more rigourous.
Try this:

 

[pillar]

Yep lol that's exactly what I was looking for, just needed to figure out how to word the statement correctly. Thanks.

 

[Timothy.Siu]

could u not use the assumption and just say

LHS=12.12^k=7.12^k+5.12^k
and 12^k>7^k, 12^k>5^k
(k.ln 12>k.ln 7)

and then continue to say
therefore LHS>RHS?