Induction help :( (1 Viewer)

[drewgcn]

I'm stuck on these questions.

Prove that 3^3n + 2^(n+2) is divisible by 5 for n>=1.

Prove that 3^n + 7^n is divisible by 10 if n is an odd integer >=1
(Hint: In step 2, assume n = k (odd); In step 3, prove true for n = k+2)

Prove that (n^2) + 2n is divisible by 8 if n is an even integer >=2.

Pre-emptive thanks .

 

[pLuvia]

Prove that 3³ⁿ + 2⁽ⁿ⁺²⁾ is divisible by 5 for n>1.
Let n = 1
35 is divisible by 5
.: S₁ is true
Assume n=k
3^3k +2^(k+2) = 5N (where N is an integer)
Let n=k+1
3^3k+3 +2^(k+3)
3^3k.3³ + 2^k.2³
Using assumption
3^3k = 5N - 2^(k+2)

(5N - 2^(k+2)).3³ + 2^k.2³
= 3³.5N - 3³2^(k+2) + 2^k+2.2
= 3³.5N - 2^(k+2)[3³ - 2]
= 3³.5N - 2^(k+2)[25]
= 5[3³.N - 2^(k+2).5
= 5M (where M is an integer)

.: If n=k is true then n=k+1 is true hence all n>1

I'll do others later

 

[pLuvia]

Prove that 3^n + 7^n is divisible by 10 if n is an odd integer n>1
(Hint: In step 2, assume n = k (odd); In step 3, prove true for n = k+2)

3ⁿ+7ⁿ
Show n = 1 is true
10 = 10
.:S₁ is true
Assume n=k
3^k+7^k=10N (where N is an integer)
Let n = k+2
3^k+2+7^k+2
From assumption
(10N-7^k)9 + 7^k.49
= 9.10N - 9.7^k + 7^k.49
= 9.10N - 7^k(9 - 49)
= 9.10N - 7^k(-40)
= 10[9+7^k.40]
= 10M (where M is an integer)
When n=k is true then n=k+2 is true hence for all n>1




Prove that (n²) + 2n is divisible by 8 if n is an even integer n>2.

n² + 2n
Show n = 2 is true
8 = 8
.: S₂ is true

Assume n = k
k² + 2k = 8N (where N is an integer)
Let n=k+2
(k+2)² + 2k+4
= k²+4k+4+2k+4
= k²+6k+8
From assumption
= (8N-2k) + 6k+8
= 16+4k
= 4[4+k]
= 4M (where M is an integer)

Since 4 is a factor of 8, it is divisble by multiple of 8s.
Hence, if n=k is true then n=k+2 is true therefore by mathematical induction n is true for all n>2

Edit: fixed it up

 

[insert-username]

From assumption
= (8-2k) + 6k+8

Shouldn't this step be (8N-2k) + 6k + 8, since N isn't necessarily 1?


Since 4 is a factor of 8, it is divisble by multiple of 8s.

If M = 1, 3, 5, 7, 9, etc. then 4M is not divisible by 8. I'm not sure whether you're right here or not - if you work it out to be something like 16M, then yes, it's always divisible by 8, but 4M is not...

Hmmm, I might just learn a little more on induction from this.


I_F

 

[drewgcn]

...
3^3k.3³ + 2^k.2³
Using assumption
3^3k = 5N - 2^(k+2)

(5N - 2^(k+2)).3³ + 2^k.2³
= 3³.5N - 3³2^(k+2) + 2^k+2.2
= 3³.5N - 2^(k+2)[3³ - 2]
= 3³.5N - 2^(k+2)[25]...

And there, good children, was the magical step!
Kudos to you pLuvia

I think I understand, I'll try the others now.

 

[drewgcn]

From assumption
= (8-2k) + 6k+8

Shouldn't this step be (8N-2k) + 6k + 8, since N isn't necessarily 1?

I think that was just a typo.

Since 4 is a factor of 8, it is divisble by multiple of 8s.

If M = 1, 3, 5, 7, 9, etc. then 4M is not divisible by 8. I'm not sure whether you're right here or not - if you work it out to be something like 16M, then yes, it's always divisible by 8, but 4M is not...

I_F

Yeah thats what's confusing me as well.

I got
Step 3: Prove true for n = k + 2
(k+2)^2 + 2(k+2) = k^2 + 4k + 4 + 2k + 4
.........................= k^2 + 2k + 4k + 8
..........................................................(k^2) + 2k = 8N from assumption
.........................= 8N + 4k + 8
.........................= 8(N + 1) + 4k

and then the 4K ruins it all.

 

[drewgcn]

I think I just got it, you guys will probably be able to tell me if so.
Continuing from the last post

.........................= 8N + 4k + 8
.........................= 8(N + 1 + k/2)
Since k is an even integer, k/2 must also be an integer.
Therefore (N + 1 + k/2) is an integer, and therefore it is true for n = k + 2.

 

[insert-username]

drewgcn, that logic works for me. Kudos!


I_F

 

[pLuvia]

I don't remember how to prove that it is divisible by 8 Can someone tell me please?

Since 4 is a factor of 8, it is divisble by multiple of 8s.

If M = 1, 3, 5, 7, 9, etc. then 4M is not divisible by 8. I'm not sure whether you're right here or not - if you work it out to be something like 16M, then yes, it's always divisible by 8, but 4M is not...

Hmmm, I might just learn a little more on induction from this.

 

[pLuvia]

From assumption
= (8-2k) + 6k+8

Shouldn't this step be (8N-2k) + 6k + 8, since N isn't necessarily 1?


I_F

Yeh sorry, typo

 

[insert-username]

If a number is divisble by 4, and then that factor is divisible by 2, then that number is divisible by 8. E.g. 4 goes into 32 eight times. 8 is divisible by 2, so 32 is divisible by 8. 4 goes into 20 five times, but 5 is not divisible by 2, so 20 iss not divisible by 8.


I_F

 

[acmilan]

Proof of what insert-username said:

Let p be an integer divisible by 4: p = 4q, where q is some integer

q is divisble by 2: q = 2r, where r is some integer

.: p = 4.2r = 8r, hence p is divisible by 8.

 

[pLuvia]

aa I see thanks acmilan

 

[Riviet]

Hmm... interesting ^.^