# Math Help - Induction

1. ## Induction

I have the question prove by induction that 5^2n-4^n is divisible by 7.

In proving p(n+1) implies P(n) I have got:

(5^2n-4^n)+ 21(5^2n-4^n) is divisible by 7 by inductive hypothesis and since 21 is divisible by 7

Just wondering if this argument holds or if anyone has any ideas?

2. Originally Posted by iwish123
I have the question prove by induction that 5^2n-4^n is divisible by 7.

In proving p(n+1) implies P(n) I have got:

(5^2n-4^n)+ 21(5^2n-4^n) is divisible by 7 by inductive hypothesis and since 21 is divisible by 7

Just wondering if this argument holds or if anyone has any ideas?
"p(n+1) implies P(n)" is backwards, should read "p(n) implies p(n+1)"

This is how my inductive step went:

$5^{2(n+1)}-4^{n+1}=25\cdot5^{2n}-4\cdot4^n\equiv4\cdot5^{2n}-4\cdot4^n\equiv4(5^{2n}-4^n)\equiv0\ \text{(mod }7\text{)}\$

3. Originally Posted by iwish123
I have the question prove by induction that 5^2n-4^n is divisible by 7.

In proving p(n+1) implies P(n) I have got:

(5^2n-4^n)+ 21(5^2n-4^n) is divisible by 7 by inductive hypothesis and since 21 is divisible by 7

Just wondering if this argument holds or if anyone has any ideas?
P(k)

$5^{2k}-4^k$ is divisible by 7

P(k+1)

$5^{2(k+1)}-4^{k+1}$ is also divisible by 7.

You can attempt to prove that $5^{2k}-4^k$ being divisible by 7 causes $5^{2k+2}-4^{k+1}$ to be divisible by 7.

This then means that if your formula is true for some n=k, it's automatically true for the next n=k+1.

Hence, if it's then true for n=1, it's true for n=2, 3, 4, 5, 6, 7, 8, to infinity.

$5^25^{2k}-(4)4^k=(25)5^{2k}-(4)4^k$

We write this "in terms of" $5^{2k}-4^k$ to get

$(21+4)5^{2k}-(4)4^k=(21)5^{2k}+4\left(5^{2k}-4^k\right)$

Hence, if $5^{2k}-4^k$ really is divisible by 7,

then, since 21 is (7)3

$5^{2(k+1)}-4^{k+1}$ will also be divisible by 7.