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?


$$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)$$

  • $\begingroup$ Remark $ $ that this proof is special case of the proof of the Congruence Product Rule, and it is much more insightful to view it in its natural congruence form - see my answer. $\endgroup$ – Bill Dubuque Sep 3 '14 at 19:10


For $n=m+1,$


$$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$


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}.$

  • $\begingroup$ Bill, I am a high school student. I am neither familiar with the Congruence Product Rule nor Modular Arithmetic so your answer is much beyond the scope of my knowledge! $\endgroup$ – user140161 Sep 3 '14 at 20:13
  • $\begingroup$ @user140161 The proof in the hint does not use congruences, only very simple arithmetic, accessible to any high-school student. if you later learn congruence arithmetic I encourage you to revisit the Remark. You will be amazed at how it greatly simplifies such matters, bringing to the fore the arithmetical essence of the matter. $\endgroup$ – Bill Dubuque Sep 3 '14 at 20:47
  • $\begingroup$ I definitely will, thanks. $\endgroup$ – user140161 Sep 10 '14 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.