# Proof by Induction Involving Divisibility

1. Feb 20, 2015

### Colleen G

1. The problem statement, all variables and given/known data
Let P(n): 7|(34n+1-52n-1. Prove that P(n) is true for every natural number n.

2. Relevant 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∈ℤ

3. 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?

2. Feb 20, 2015

### Dick

Here's a short hint 3^4=81=56+25=56+5^2 and 56 is divisible by 7.

3. Feb 21, 2015

### 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?

4. Feb 21, 2015

### Dick

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

5. Feb 21, 2015

### Ray Vickson

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$.

6. Feb 21, 2015

### Colleen G

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