Proof by induction

  • Thread starter deryk
  • Start date
  • #1
10
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
VietDao29
Homework Helper
1,417
1
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
10
0
How did you get from:

5^(k+1) -4(k+1) + 15 = 5^k - 4k + 15 + 4(5^k -1)
 
  • #4
VietDao29
Homework Helper
1,417
1
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
Galileo
Science Advisor
Homework Helper
1,989
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
67
0
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
Galileo
Science Advisor
Homework Helper
1,989
6
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
67
0
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:
 

Related Threads for: Proof by induction

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
4
Views
8K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
2
Views
2K
Replies
4
Views
2K
Top