Mathmatical Induction

Question

Prove, by mathmatical induction, that $5^{2n}$ + $2^{2n-2}$$3^{n-1}$ is divisible by $13$. I first plugged in n as 1 and showed that the expression is divisible by 13 for n=1. Then I assumed that the expression was divisible by 13 for n=k and plugged in k. The simplified expression in terms of k was $25^k$ + $\frac{4^n3^n}{12}$. I then plugged in k+1 and got an expression for that. I am unable to show that the sum or difference of the k and k+1 expressions is divisible by 13. How do I proceed?

Answer 1

$$25^{k+1}+\frac{4^{k+1}3^{k+1}}{12}=25\cdot 25^{k}+12 \frac{4^{k}3^{k}}{12} $$

$$=13\cdot 25^k+12\cdot25^k+12 \frac{4^{k}3^{k}}{12} $$

$$=13\cdot 25^k + 12 \left(25^k+ \frac{4^{k}3^{k}}{12}\right)$$

Answer 2

HINT:

For $n=m+1,$

$$f(m+1)=25^{m+1}+4^m3^m=25^{m+1}+12^m$$

$$f(m+2)-25f(m+1)=25^{m+2}+12^{m+1}-25(25^{m+1}+12^m)=-12^m(25-12)$$ $$\implies f(m+2)-25f(m+1)\equiv0\pmod{13}$$

Alternatively, $$f(m+2)-12f(m+1)=25^{m+1}(25-12)\equiv0\pmod{13}$$

By either method, $f(m+2)$ will be divisible by $13$ if $13|f(m+1)$

Now establish the base case i.e., for $n=1$

Answer 3

Hint $\ \ \ 25^{n+1}\!+12^n =\, (\underbrace{25\!-\!12}_{\large\color{#c00}{=\, 13}})\,25^n + 12\,(\!\!\!\!\!\underbrace{25^n+12^{n-1}}_{\large\color{#c00}{=\, 13\,k}\rm\ by\ induction}\!\!\!\!\!\!)\ $ is divisible by $\,\color{#c00}{13}\ \ $ QED

Remark $\ $ More intuitively, use the Congruence Product Rule to multiply the first two congruences below to deduce the third, $ $ yielding the induction step $\,P(n)\,\Rightarrow\, P(n\!+\!1)$.

$$ \begin{eqnarray}{\rm mod}\ 13\!:\quad\ 25&\equiv&\ \ \ 12\\ 25^n&\equiv&\!\! {-}\!12^{n-1}\ \ \ {\rm i.e.}\ \ \ P(n)\\ \Rightarrow\ 25^{n+1} &\equiv&\!\! {-}\!12^n\quad\ \ \, {\rm i.e.}\ \ \ P(n\!+\!1) \end{eqnarray}\qquad\qquad\qquad$$

The proof in the hint arises in the following mechanical manner: take the standard proof of the Congruence Product Rule in the linked post, then substitute the specific numbers in this problem, i.e. we simply repeated the proof for the special case at hand. Though many such inductive proofs appear to be pulled out of a hat like magic, in fact they are, at heart, instances of congruence arithmetic - exactly as above. Once you learn congruence arithmetic the problem becomes trivial: it boils down to $\, (-1)^{n+1}\equiv\, -(-1)^n\ $ since $\ 25\equiv -1 \equiv 12\pmod{13}.$