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.