1. ## Induction proof

Good night.

Prove by induction that $4^{2n+1}+3^{n+2}$ is a multiple of $13$ for all values of $n\geq{0}$.

All help much appreciated.

2. For n=0

$4^{2n+1}+3^{n+2}=4+9=13$, which is a multiple of 13.

3. Originally Posted by I-Think
Good night.

Prove by induction that $4^{2n+1}+3^{n+2}$ is a multiple of $13$ for all values of $n\geq{0}$.

All help much appreciated.
Base case: n = 0:
$4^{2(0)+1}+3^{0+2} = 4^1 + 3^2 = 13$ OK.

Assume that $4^{2n+1}+3^{n+2}$ holds true for n = k.
$4^{2k + 1} + 3^{k + 2}$ is divisible by 13.

Prove that it holds true for n = k + 1:
$4^{2(k + 1) + 1} + 3^{(k + 1) +2}$
\begin{aligned}
&= 4^{2k + 3} + 3^{k + 3} \\
&= 16 \cdot 4^{2k + 1} + 3 \cdot 3^{k + 2} \\
&= (13 + 3)\cdot 4^{2k + 1} + 3 \cdot 3^{k + 2} \\
&= 13\cdot 4^{2k + 1} + 3\cdot 4^{2k + 1} + 3 \cdot 3^{k + 2} \\
&= 13\cdot 4^{2k + 1} + 3(4^{2k + 1} + 3^{k + 2})
\end{aligned}

In this final sum, the first addend is obviously divisible by 13, and since what's inside the parentheses is divisible by 13, so is the second addend. Thus the final sum is divisible by 13.

01