Proof by Induction Involving Divisibility

Colleen G
Messages
6
Reaction score
0

Homework Statement


Let P(n): 7|(34n+1-52n-1. Prove that P(n) is true for every natural number n.

Homework Equations


*I know that proving by induction requires a proving P(1) true, and then proving P(k+1) true.
*If a|b, then b=a*n, for some n∈ℤ

The Attempt at a Solution


I have proved the "base case" for P(1). Long story short, for n=1, you wind up with 7|238 by definition of divisibility since 238=7(34). So P(1) is true.

The next part is where it gets tricky - Assuming P(k) is true, that is, 7|(34k+1-52k-1, which is the inductive hypothesis. Then proving for P(k+1). What I have so far is...
7|7|(34(k+1)+1-52(k+1)-1
=34k+5-52k+1
=34 * 34k+1-51*52k
=34 * 34k+1-(3*52k+2*52k)
=34 * 34k+1-3*52k-2*52k
=.....

Now I don't know what to do! I know I have to get it to the point where I can use the inductive hypothesis, which is what I'm trying to do, but I've hit a wall, or taken a wrong turn when split the 5 into a two and a three. Any ideas?
 
Physics news on Phys.org
Colleen G said:

Homework Statement


Let P(n): 7|(34n+1-52n-1. Prove that P(n) is true for every natural number n.

Homework Equations


*I know that proving by induction requires a proving P(1) true, and then proving P(k+1) true.
*If a|b, then b=a*n, for some n∈ℤ

The Attempt at a Solution


I have proved the "base case" for P(1). Long story short, for n=1, you wind up with 7|238 by definition of divisibility since 238=7(34). So P(1) is true.

The next part is where it gets tricky - Assuming P(k) is true, that is, 7|(34k+1-52k-1, which is the inductive hypothesis. Then proving for P(k+1). What I have so far is...
7|7|(34(k+1)+1-52(k+1)-1
=34k+5-52k+1
=34 * 34k+1-51*52k
=34 * 34k+1-(3*52k+2*52k)
=34 * 34k+1-3*52k-2*52k
=.....

Now I don't know what to do! I know I have to get it to the point where I can use the inductive hypothesis, which is what I'm trying to do, but I've hit a wall, or taken a wrong turn when split the 5 into a two and a three. Any ideas?

Here's a short hint 3^4=81=56+25=56+5^2 and 56 is divisible by 7.
 
Ok yes I see that, but am having trouble using it. Are the steps that I have taken so far correct? Or have I done more than necessary. What I'm saying is, can I use this information about 3^4 from the step that I left off at?
 
Colleen G said:
Ok yes I see that, but am having trouble using it. Are the steps that I have taken so far correct? Or have I done more than necessary. What I'm saying is, can I use this information about 3^4 from the step that I left off at?

Convince yourself that ##P(k+1)=81*3^{4k+1}-25*5^{2k-1}##. Use that ##81=56+25##. See how you can express that in terms of ##P(k)##?
 
Colleen G said:

Homework Statement


Let P(n): 7|(34n+1-52n-1. Prove that P(n) is true for every natural number n.

Homework Equations


*I know that proving by induction requires a proving P(1) true, and then proving P(k+1) true.
*If a|b, then b=a*n, for some n∈ℤ

The Attempt at a Solution


I have proved the "base case" for P(1). Long story short, for n=1, you wind up with 7|238 by definition of divisibility since 238=7(34). So P(1) is true.

The next part is where it gets tricky - Assuming P(k) is true, that is, 7|(34k+1-52k-1, which is the inductive hypothesis. Then proving for P(k+1). What I have so far is...
7|7|(34(k+1)+1-52(k+1)-1
=34k+5-52k+1
=34 * 34k+1-51*52k
=34 * 34k+1-(3*52k+2*52k)
=34 * 34k+1-3*52k-2*52k
=.....

Now I don't know what to do! I know I have to get it to the point where I can use the inductive hypothesis, which is what I'm trying to do, but I've hit a wall, or taken a wrong turn when split the 5 into a two and a three. Any ideas?

This is badly written: the "equation" you wrote, namely
7|7|(3^{4(k+1)+1} - 5^{2(k+1)-1} \\<br /> = 3^{4k+5} - 5^{2k+1} \\<br /> \vdots<br />
does not even make sense.

To say it properly, here is a hint: letting ##F(n) = 3^{4n+1} - 5^{2n-1}##, prove that for positive integer ##k##, ##F(k) = 7j## for some positive integer ##j## implies ##F(k+1) = 7 m## for some positive integer ##m##.
 
Thank you for you help, Dick! I understand now.
 
There are two things I don't understand about this problem. First, when finding the nth root of a number, there should in theory be n solutions. However, the formula produces n+1 roots. Here is how. The first root is simply ##\left(r\right)^{\left(\frac{1}{n}\right)}##. Then you multiply this first root by n additional expressions given by the formula, as you go through k=0,1,...n-1. So you end up with n+1 roots, which cannot be correct. Let me illustrate what I mean. For this...
Back
Top