Proving 5^n-4n+15 Divisible by 16

[deryk]

I need to prove by mathematical induction that all positive numbers of the form 5^n-4n+15 are divisible by 16 where n is a natural number(1,2,3,4,5...).

So far
P(1) = 5^1-4*1+15 = 16 true for P(1)
AssumeP(k) is true.

5^k-4k + 15 is disible by 16.

Now for P(k+1)

P(k+1)=5^(k+1) -4(k+1)+ 15 I don't know how to prove it is divisible by 16?

Normally with these the P(k+1) usually equals a sum of 2 numbers that collecting like terms,etc. comes to the same style as the original equation except with k+1 where n is. Thanks for your time.

 

[VietDao29]

So you know:
5 ^ k - 4k + 15 is divisible by 16.
You will try to arrange 5 ^ {k + 1} - 4(k + 1) + 15 into something like:
5 ^ k - 4k + 15 + ? Since 5 ^ k - 4k + 15 is divisible by 16, you just need to prove '?' is divisible by 16.
Here we go:
5 ^ {k + 1} - 4(k + 1) + 15 = ... = 5 ^ k - 4k + 15 + 4(5 ^ k - 1)
You need to prove 4(5 ^ k - 1) is divisible by 16. In other words, you need to prove: 5 ^ k - 1 is divisible by 4 (You can prove this by induction or:
a ^ {\alpha} - 1 = (a - 1)(a ^ {\alpha - 1} + a ^ {\alpha - 2} + a ^ {\alpha - 3} + ... + a ^ {2} + a + 1}) \mbox{, }\alpha \in \mathbb{N} ^ *).
Viet Dao,

 

[deryk]

How did you get from:

5^(k+1) -4(k+1) + 15 = 5^k - 4k + 15 + 4(5^k -1)

 

[VietDao29]

Okay, so you notice: In 5 ^ {k + 1} - 4(k + 1) + 15, there is -4k, and + 15, but there is no 5 ^ k, so you will plus and then subtract 5 ^ k:
5 ^ {k + 1} - 4(k + 1) + 15 = 5 ^ {k + 1} - 4k - 4 + 15 = 5 ^ k - 4k + 15 + 5 ^ {k + 1} - 5 ^ k - 4 = ...
Can you go from here?
Viet Dao,

 

[murshid_islam]

5 ^ {k + 1} - 4(k + 1) + 15
=5*5^k-4k-4+15
=5^k+4*5^k-4k-4+15
=5^k-4k+15+4(5^k-1)

where '*' means multiplication

 

[Galileo]

Deryk, the way to solve an induction problem like this is to make maximum use of your induction hypothesis.
If you have the expression:

5^{k+1}-4(k+1)+15 = 5 \cdot 5^k-4k +11
and you assume that
5^k-4k +15
is divisible by 16, then you should try to get this expression for P(k) into your expression for P(k+1).
How to do that? The most obvious way seems to be to factor out the 5, right? That'll bring the 5^(k+1) back to 5^k and we can worry about the rest later. So you get:

5(5^k-4k+15)+ 16k-64

 

[monet A]

Deryk, the way to solve an induction problem like this is to make maximum use of your induction hypothesis.
If you have the expression:

5^{k+1}-4(k+1)+15 = 5 \cdot 5^k-4k +11
and you assume that
5^k-4k +15
is divisible by 16, then you should try to get this expression for P(k) into your expression for P(k+1).
How to do that? The most obvious way seems to be to factor out the 5, right? That'll bring the 5^(k+1) back to 5^k and we can worry about the rest later. So you get:

5(5^k-4k+15)+ 16k-64

I can see that:

5(5^k-4k+15)+ 16k-64

Is equal to P(k) + 16(n element of reals)

But I m not sure I understand how it was induced into the equation.

Here is where I am stuck.

I've found:

5 \cdot 5^k-4k +11

naturally.

The difference between 5\cdot 5^k and (5^k-4k+15) is 5\cdot(-4k+15)

therefore it is necessary to add 5\cdot(-4k+15) to -4k and +11 to complete the equation. It seems to me to be right except if it is I have a sign problem.

I am learning induction too so it is helpful for me to work through this problem now, can you tell me which part I have done wrong.

 

[Galileo]

It doesn't need to be that complicated. You want add something to 5(5^k-4k+15) to make it equal to 5 \cdot 5^k-4k +11 in order to get the same equation. Clearly you already have the 5\cdot 5^k, you have -20k, so you add 16k to get -4k, and you have (5)(15)=75, so you subtract 64 to get 11.

5(5^k-4k+15)+ 16k-64=5\cdot 5^k-4k+11

I hope that was clear enough, it's just arithmetic. Don't know how to explain it better.

 

[monet A]

It doesn't need to be that complicated. You want add something to 5(5^k-4k+15) to make it equal to 5 \cdot 5^k-4k +11 in order to get the same equation. Clearly you already have the 5\cdot 5^k, you have -20k, so you add 16k to get -4k, and you have (5)(15)=75, so you subtract 64 to get 11.

5(5^k-4k+15)+ 16k-64=5\cdot 5^k-4k+11

I hope that was clear enough, it's just arithmetic. Don't know how to explain it better.

Thanks Galileo for your reply, I worked out my mistake before I got here it was just a stupid mistake of adding and adding dumb really.

I just wanted to say that your explanation has helped me the most to grasp the concepts so thanks Reaallly much.