Prove $24\mid5^{2n}+12n^2-36n-1$ using induction

Question

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction

What I thought:

Inductive hipothesis: $$ 5^{2n}+12n^2-36n-1=24k $$

Inductive step: $$ 5^{2(n+1)}+12(n+1)^2-36(n+1)-1=24q $$ $k,q \in \mathbb{Z}$ Then I tried doing all sorts of factoring but couldn't get quite there, what strategies should I use in these sort of problems?

E: $5^{2(n+1)}\neq5^{2n+1}...$

Answer 1

Hint:

$$5^{2(n+1)}+12(n+1)^2-36(n+1)-1=$$$$=\underbrace{(24\cdot 5^{2n}+24n+12-36)}_{\text{trivially divisible by }24}+\underbrace{(5^{2n}+12n^2-36n-1)}_{\text{inductive hypothesis}}$$

---

Alternatively, $$5^{2n}+12n^2-36n-1=(25^n-1^n)+12(n^2-3n)$$

Here $25^n-1^n=(25-1)(25^{n-1}+25^{n-2}+\cdots+25+1)$ and $n^2-3n$ is even.

Answer 2

One can easily verify that this function $f(n)$ satisfies the following recursion: $$f(n) = 28f(n-1)-78f(n-2)+76f(n-3)-25f(n-4)$$

Therefore by induction it is enough to check it for $n = 1, 2, 3, 4$.

Answer 3

Hint $\ $ It is $\, (25^n\!-\!1) + 12n(n\!-\!1)-24n\,$ so it suffices to show $\,24\mid 25^n\!-\!1,\,\ 2\mid n(n\!-\!1),\,$ both of which are well-known (or easily proved by induction, and more conceptually so).

Answer 4

First, show that this is true for $n=1$:

$5^{2\cdot1}+12\cdot1^2-36\cdot1-1=0$

Second, assume that this is true for $n$:

$5^{2n}+12n^2-36n-1=24k$

Third, prove that this is true for $n+1$:

$5^{2(n+1)}+12(n+1)^2-36(n+1)-1=$

$25\cdot5^{2n}+12n^2-12n-25=$

$25\cdot(\color{red}{5^{2n}+12n^2-36n-1})+888n-288n^2=$

$25\cdot\color{red}{24k}+888n-288n^2=$

$25\cdot24k+24\cdot(37n-12n^2)=$

$24\cdot(25k+37n-12n^2)$

---

Please note that the assumption is used only in the part marked red.