Induction (1 Viewer)

[cutemouse]

Prove by mathematical induction that (3n+1)(7ⁿ) - 1 is divisible by 9 for all integers n≥1.

Thanks

 

[oly1991]

ill skip a few steps...

Assume n=k

(3k+1)(7^k) -1 = 9M (where M is an integer) also 7^k = 9M+1/(3k+1)

for n=k+1

(3k+4)(7^k.7^1) - 1 sub in 7^k from above
(3k+4)(63M+1/3k+1) - 1
manipulate this and u get:
9(21kM + 2k + 28M +3) which is divisible by 9 because it is a common factor

i think thats it....but im not sure cos i rushed it

 

[cutemouse]

Hmm, I think that's different from what I got. Anyone else?

 

[Pwnage101]

i too shall skip a few steps

assume n=k is true, ie assumes (3k+1)7^k-1=9Q, Q a positive integer

k+1 statement is:

(3(k+1)+1)7^(k+1)-1

=(7)(7^k)(3k+3+1)-1
=(7)(7^k)(3k+4)-1
=(7)(7^k)((3k+1)+3)-1
=(7)(7^k)(3k+1)+(7)(7^k)(3)-1
=(7)[(7^k)(3k+1)-1]+7+(7)(7^k)(3)-1
=(7)(9Q)+(7)(7^k)(3)+6

now from our initial statement,

(3k+1)7^k-1=9Q

rearranging gives us

7^k=(9Q+1)/(3k+1)

change k into (k+1) and we get

7^(k+1)=(9Q+1)/(3k+4)


sub this in and we get

=(7)(9Q)+(7)(7^k)(3)+6
=(7)(9Q)+(7^(k+1))(3)+6
=(7)(9Q)+[(9Q+1)/(3k+4)](3)+6
=(7)(9Q)+[(9Q+1)/(3k+4)](3)+6(3k+4)/(3k+4)
=(7)(9Q)+[1/(3k+4)][(9Q+1)(3)+6(3k+4)]
=(7)(9Q)+[1/(3k+4)][(9Q+1)(3)+18k+24]
=(7)(9Q)+[1/(3k+4)][27Q+3+18k+24]
=(7)(9Q)+[1/(3k+4)][27Q+18k+27]
=(7)(9Q)+[1/(3k+4)](9)[3Q+2k+3]
=9[7Q+[1/(3k+4)][3Q+2k+3]]

which is divisible by 9

however not sure about the [1/(3k+4)][3Q+2k+3] term and justifying thats an integer though.

I also rushed this, so please do chek.

 

[cutemouse]

change k into (k+1) and we get

7^(k+1)=(9Q+1)/(3k+4)

Hmm, can you do that?

 

[Pwnage101]

Hmm, can you do that?

i think so,

because consider 7^(k)=(9Q+1)/(3k+1)

let k = n+1

thus 7^(n+1)=(9Q+1)/(3(n+1)+1)=7^(n+1)=(9Q+1)/(3n+4)

just swap n bak to k - theya re both dummy variables

if you dont like it, just change 7^(k+1) into 7.7^k, and sub in the statement for 7^k bak in, and youll just get a 7 hanging around, shouldnt change much

 

[Trebla]

Prove by mathematical induction that (3n+1)(7ⁿ) - 1 is divisible by 9 for all integers n≥1.

Thanks

You have to prove 6 + 3.7ⁿ⁺¹ is divisible by 9 by induction first, then use that result to prove the other result.

 

[cutemouse]

I don't get why you can just assume the result for k+1, isn't that what we're trying to prove?

 

[gurmies]

Not quite. You assume the result is true for n = k and then write out the expression for k+1. In all cases where induction is asked, the k+1 can be turned into a k with other parts, which is where you can sub in your assumption...