Use mathematical induction to prove that $5^{2n+1}$ + $3^{2n+1}$ is divisible by $4$ for all natural numbers $n$.

Question

Use mathematical induction to prove that $5^{2n+1}$ + $3^{2n+1}$ is divisible by $4$ for all natural numbers $n$.

I hope I'm going in the right direction at least. Here is where I got to so far:

When $n = 0$, we have $5^{2(0)+1} + 3^{2(0)+1} = 8$, so statement holds.

Assume statement holds for $n = k$.

So $5^{2k+1} + 3^{2k+1} = 4p$ for some $p$

When $n = k + 1$, we have:

$5^{2k+3} + 3^{2k+3}$ which can be rewritten as $(125 \times 5^{2k}) + (27 \times 3^{2k})$

$125 = 4 \times 31 + 1$

$27 = 4 \times 6 + 3$

$(125 \times 5^{2k}) + (27 \times 3^{2k}) = (4 \times 31 + 1) \times 5^{2k} + (4 \times 6 + 3) \times 3^{2k}$

I am trying to take out the factor of $4$, but I'm not sure how to do that correctly, or if that is even the right thing to do.

Answer 1

You are fine up until:

Show $5^{2k+3} + 3^{2k+3}$ is divisible by 4 given $4|5^{2k+1} + 3^{2k+1}$

We want to get the exponents on the left to look as much as possible like the exponents on the right

$(5^2)5^{2k+1} + (3^2)3^{2k+1}\\ (25)5^{2k+1} + (9)3^{2k+1}\\ (24)5^{2k+1} + (8)3^{2k+1}+5^{2k+1} + 3^{2k+1}\\ $

The first two terms are clearly divisible by 4, and the last two, taken together, are divisible by 4 based on the inductive hypothesis.

Answer 2

Hint: do something similar but to $$25 \cdot 5^{2k +1} + 9 \cdot 3^{2k+1} = 16 \cdot 5^{2k +1} + 9 \cdot \left(5^{2k+1} + 3^{2k+1} \right).$$ Why is this divisible by $4$?