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

In summary, to prove that all positive numbers of the form 5^n-4n+15 are divisible by 16, we first use mathematical induction. We show that P(1) = 16, and then assume that P(k) is true, where 5^k-4k+15 is divisible by 16. Then, to prove P(k+1), we manipulate the given equation to get 5^(k+1)-4(k+1)+15 into a similar form as P(k), i.e. 5^k-4k+15. This is achieved by adding and subtracting certain terms, ultimately leading to the equation 5(5^k-4k+15)+16k-
  • #1
deryk
10
0
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.
 
Mathematics news on Phys.org
  • #2
So you know:
[tex]5 ^ k - 4k + 15[/tex] is divisible by 16.
You will try to arrange [tex]5 ^ {k + 1} - 4(k + 1) + 15[/tex] into something like:
[tex]5 ^ k - 4k + 15 + ?[/tex] Since [tex]5 ^ k - 4k + 15[/tex] is divisible by 16, you just need to prove '?' is divisible by 16.
Here we go:
[tex]5 ^ {k + 1} - 4(k + 1) + 15 = ... = 5 ^ k - 4k + 15 + 4(5 ^ k - 1)[/tex]
You need to prove [tex]4(5 ^ k - 1)[/tex] is divisible by 16. In other words, you need to prove: [tex]5 ^ k - 1[/tex] is divisible by 4 (You can prove this by induction or:
[tex]a ^ {\alpha} - 1 = (a - 1)(a ^ {\alpha - 1} + a ^ {\alpha - 2} + a ^ {\alpha - 3} + ... + a ^ {2} + a + 1}) \mbox{, }\alpha \in \mathbb{N} ^ *[/tex]).
Viet Dao,
 
  • #3
How did you get from:

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

where '*' means multiplication
 
Last edited:
  • #6
Deryk, the way to solve an induction problem like this is to make maximum use of your induction hypothesis.
If you have the expression:

[tex]5^{k+1}-4(k+1)+15 = 5 \cdot 5^k-4k +11[/tex]
and you assume that
[tex]5^k-4k +15[/tex]
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:

[tex]5(5^k-4k+15)+ 16k-64[/tex]
 
  • #7
Galileo said:
Deryk, the way to solve an induction problem like this is to make maximum use of your induction hypothesis.
If you have the expression:

[tex]5^{k+1}-4(k+1)+15 = 5 \cdot 5^k-4k +11[/tex]
and you assume that
[tex]5^k-4k +15[/tex]
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:

[tex]5(5^k-4k+15)+ 16k-64[/tex]


I can see that:

[tex]5(5^k-4k+15)+ 16k-64[/tex]

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:

[tex] 5 \cdot 5^k-4k +11[/tex]

naturally.

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

therefore it is necessary to add [itex] 5\cdot(-4k+15) [/itex] 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.
 
  • #8
It doesn't need to be that complicated. You want add something to [itex]5(5^k-4k+15)[/itex] to make it equal to [itex]5 \cdot 5^k-4k +11[/itex] in order to get the same equation. Clearly you already have the [itex]5\cdot 5^k[/itex], you have -20k, so you add 16k to get -4k, and you have (5)(15)=75, so you subtract 64 to get 11.

[tex]5(5^k-4k+15)+ 16k-64=5\cdot 5^k-4k+11[/tex]

I hope that was clear enough, it's just arithmetic. Don't know how to explain it better.
 
  • #9
Galileo said:
It doesn't need to be that complicated. You want add something to [itex]5(5^k-4k+15)[/itex] to make it equal to [itex]5 \cdot 5^k-4k +11[/itex] in order to get the same equation. Clearly you already have the [itex]5\cdot 5^k[/itex], you have -20k, so you add 16k to get -4k, and you have (5)(15)=75, so you subtract 64 to get 11.

[tex]5(5^k-4k+15)+ 16k-64=5\cdot 5^k-4k+11[/tex]

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. :rolleyes:

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

What is the problem "Proving 5^n-4n+15 Divisible by 16" all about?

The problem is to determine whether the expression 5^n-4n+15 is divisible by 16 for all values of n. In other words, we need to prove that the expression always results in a whole number when divided by 16.

Why is it important to prove the divisibility of 5^n-4n+15 by 16?

Proving the divisibility of this expression is important because it can help us understand the patterns and properties of numbers. It also has practical applications in fields such as cryptography and computer science.

What is the general approach to proving the divisibility of an expression?

The general approach to proving the divisibility of an expression is to use mathematical induction. This involves showing that the expression is true for a base case (usually n=0 or n=1) and then assuming it is true for a given value of n and proving that it is also true for n+1. This process is repeated until we can prove that the expression is true for all values of n.

How can we prove that 5^n-4n+15 is divisible by 16 using mathematical induction?

We can prove the divisibility of 5^n-4n+15 by 16 using mathematical induction by first showing that the expression is true for n=0. Then, we assume that it is true for a given value of n and prove that it is also true for n+1. This can be done by substituting n+1 into the expression and simplifying until it can be written as 16k for some integer k. This completes the inductive step, and by the principle of mathematical induction, we can conclude that the expression is divisible by 16 for all values of n.

Are there any other methods for proving the divisibility of an expression?

Yes, there are other methods for proving the divisibility of an expression, such as using the properties of modular arithmetic or divisibility rules for specific numbers. However, mathematical induction is a widely used and effective method for proving divisibility.

Similar threads

Replies
5
Views
2K
Replies
13
Views
1K
  • General Math
Replies
8
Views
2K
Replies
7
Views
3K
  • General Math
Replies
3
Views
1K
Replies
68
Views
9K
  • General Math
Replies
11
Views
2K
  • General Math
Replies
7
Views
2K
Replies
4
Views
381
Back
Top