1. ## Induction Problem

This problem I could not solve

Use induction to prove that
$\displaystyle 3^{4n+2} + 5^{2n+1}$ is divisible to 14

2. Originally Posted by Apprentice123
This problem I could not solve

Use induction to prove that
$\displaystyle 3^{4n+2} + 5^{2n+1}$ is divisible to 14
Induction.
First, we verify a "base case". (like n = 1) I'll assume n is a natural number.

base case: (n = 1)
3^(4+2) + 5^(2+1) = 3^7 + 5^3 = 854. (( 854/14 = 61. so we are good here)

induction step:
Suppose that P(n) is true. That is to say, suppose "3^(4n+2) + 5^(2n+1) is divisible by 14)" = "3^(4n+2) + 5^(2n+1) = 14k for some k" (1)
Show P(n+1) is true.

3^(4(n+1)+2) + 5^(2(n+1)+1)
= 3^(4n+6) + 5^(2n+3)
= 3^4 * 3^(4n+2) + 5^2 * 5^(2n+1)
substitute using (1)
= 81 * 3^(4n+2) + 25 * (14k - 3^(4n+2))
= 81 * 3^(4n+2) - 75 *3^(4n+2) + 25*14k
= 6 * 3^(4n+2) + 25*14k

...
I've made a mistake somewhere in my algebra, b/c 6*3^(4n+2) for n=1 is not divisible by 14. sorry I can't find it (sleepy) but you get the idea?

3. Originally Posted by Apprentice123
This problem I could not solve

Use induction to prove that
$\displaystyle 3^{4n+2} + 5^{2n+1}$ is divisible to 14
I will let you check the case $\displaystyle n=1$.

So suppose the statement is true for $\displaystyle n = k-1$, then $\displaystyle 14| 3^{4k - 2} + 5^{2k-1}$

To prove the statement is true for $\displaystyle n = k$, check:
$\displaystyle 3^{4k + 2} + 5^{2k+1} = 25.(3^{4k-2} + 5^{2k-1}) + 14.3^{4k-1} + 14$

From induction hypothesis, $\displaystyle 14|25.(3^{4k-2} + 5^{2k-1})$ and the rest of the terms are clearly divisible by 14. Thus $\displaystyle 14|3^{4k + 2} + 5^{2k+1}$

4. My solution

n=k
$\displaystyle 3^{4k+2} + 5^{2k+1} = 14m$
$\displaystyle 3^{4k+6} + 5^{2k+3} = 854m$
$\displaystyle 3^{4k+6} + 5^{2k+3} = 14(61m)$

61m is integer and $\displaystyle 3^{4k+6} + 5^{2k+3}$ is divisible by 14

Are Correct ?

5. Originally Posted by Apprentice123
My solution

n=k

$\displaystyle 3^{4k+2} + 5^{2k+1} = 14m$

$\displaystyle 3^{4k+6} + 5^{2k+3} = 854m$

You'd need to clarify that 2nd line

$\displaystyle 3^{4k+6} + 5^{2k+3} = 14(61m)$

61m is integer and $\displaystyle 3^{4k+6} + 5^{2k+3}$ is divisible by 14

Are Correct ?
P(k)

$\displaystyle 3^{4k+2}+5^{2k+1}\text{\footnotesize\;\;\;is\ divisible\ by\;\;\;}14\ ?$

P(k+1)

P(k) being true (if it is) causes

$\displaystyle 3^{4(k+1)+2}+5^{2(k+1)+1}\text{\footnotesize\;\;\; to\ also\ be\ divisible\ by\;\;\;}14\ ?$

Proof

$\displaystyle 3^{4k+6}+5^{2k+3}=3^43^{4k+2}+5^25^{2k+1}$

$\displaystyle 3^4=81,\ 5^2=25, 5^2+56=3^4$

$\displaystyle 25\left(3^{4k+2}+5^{2k+1}\right)+(56)3^{4k+2}\text {\footnotesize\;\;\;is\ divsible\ by\;\;\;}14\ ?$

$\displaystyle 56=4(14)$

therefore if P(k) is true, then it causes P(k+1) to be true.

To find out if P(k) is true in general, test it for the initial value of n or k.