# Mathmatical Induction

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? ## 3 Answers$$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)$$• 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. – Bill Dubuque Sep 3 '14 at 19:10 HINT: For n=m+1,$$f(m+1)=25^{m+1}+4^m3^m=25^{m+1}+12^mf(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}.\$

• 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! – user140161 Sep 3 '14 at 20:13
• @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. – Bill Dubuque Sep 3 '14 at 20:47
• I definitely will, thanks. – user140161 Sep 10 '14 at 17:01