Proof by Induction Involving Divisibility

[Colleen G]

Homework Statement

Let P(n): 7|(3⁴ⁿ⁺¹-5^2n-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|(3^4k+1-5^2k-1, which is the inductive hypothesis. Then proving for P(k+1). What I have so far is...
7|7|(3^4(k+1)+1-5^2(k+1)-1
=3^4k+5-5^2k+1
=3⁴ * 3^4k+1-5¹*5^2k
=3⁴ * 3^4k+1-(3*5^2k+2*5^2k)
=3⁴ * 3^4k+1-3*5^2k-2*5^2k
=.....

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?

 

[Dick]

Homework Statement

Let P(n): 7|(3⁴ⁿ⁺¹-5^2n-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|(3^4k+1-5^2k-1, which is the inductive hypothesis. Then proving for P(k+1). What I have so far is...
7|7|(3^4(k+1)+1-5^2(k+1)-1
=3^4k+5-5^2k+1
=3⁴ * 3^4k+1-5¹*5^2k
=3⁴ * 3^4k+1-(3*5^2k+2*5^2k)
=3⁴ * 3^4k+1-3*5^2k-2*5^2k
=.....

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.

 

[Colleen G]

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?

 

[Dick]

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)$?

 

[Ray Vickson]

Homework Statement

Let P(n): 7|(3⁴ⁿ⁺¹-5^2n-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|(3^4k+1-5^2k-1, which is the inductive hypothesis. Then proving for P(k+1). What I have so far is...
7|7|(3^4(k+1)+1-5^2(k+1)-1
=3^4k+5-5^2k+1
=3⁴ * 3^4k+1-5¹*5^2k
=3⁴ * 3^4k+1-(3*5^2k+2*5^2k)
=3⁴ * 3^4k+1-3*5^2k-2*5^2k
=.....

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} \\ = 3^{4k+5} - 5^{2k+1} \\ \vdots$$
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$.

 

[Colleen G]

Thank you for you help, Dick! I understand now.