Prove that for all $n \in \mathbb{N}$, either 3 or 13 divides $3^n + 13n^2 + 38$ Let $a\in \{3,13\}.$ I'm having trouble with this proof. I know that
$$3^{n+1} + 13(n+1)^2 + 38 = (3^n + 13n^2 + 38) + (2\cdot 3^n + 26n + 13)$$
But I can't prove that $a \mid 2\cdot3^n + 26n + 13$. I know that 13 doesn't divide this because $13 \nmid 2\cdot3^n$. How can I prove that $3 \mid 26n + 13$?
 A: For $n\ge1,$
$$f(n)=3^n+13n^2+38\equiv n^2-1\pmod3$$
So,
$$3\mid f(n)\iff n\equiv\pm1\iff3\nmid n\iff(n,3)=1$$
Again
$$3^n+13n^2+38\equiv3^n-1\pmod{13}$$ which holds true if $3\mid n$ as $3^3\equiv1\pmod{13}$
A: You had the tag induction, so here's an answer by induction.
Base cases:
$n=0:  3^n+13n^2+38\equiv1+38\equiv39\equiv0\mod{13}$.
$n=1:  3^n+13n^2+38\equiv3+13+38\equiv54\equiv0\mod3$.
$n=2:  3^n+13n^2+38\equiv9+52+38\equiv99\equiv0\mod3$.
Inductive step:
$3^{n+3}+13(n+3)^2+38=3^n+13n^2+38+26\times3^n+78n+117$
$\equiv 3^n+13n^2+38 \mod 3$ or $13$.
A: If $n\equiv1$ or $2\pmod3$ then $3^n+13n^2+38\equiv n^2+2\equiv0 \pmod 3$
because $3^n\equiv0$ and $13\equiv1$ and $38\equiv2 \pmod 3$, so $3|3^n+13n^2+38$.
If $n\equiv0\pmod3$ then $3^n+13n^2+38\equiv 1+12\equiv0\pmod { 13}$
because $3^3=27\equiv1 $ and $13\equiv0$ and $38\equiv12 \pmod {13}$, so $13|3^n+13n^2+38$.
A: Define $f(n) =  3^n + 13n^2 + 38$.
Using algebra it can be shown that for all $n \ge 0$ we have the following identities,
$\tag 1 f(n+1) = 3 f(n) -26 n^2 + 26 n -63$
$\tag 2 f(n+2) = 9 f(n) -104 n^2 + 52 n -252$
$\tag 3 f(n+3) = 27 f(n) -338 n^2 + 78 n -871 =$
$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \; \; \, \quad \quad  27  f(n) -13 (26 n^2 - 6 n + 67)$
By $\text{(3)}$, whenever $13 \mid f(n)$ it must also be true that $13 \mid f(n+3)$. Snce $f(0)) = 39$,
$\tag 4 13 \text{ divides every number in } \{f(0), f(3), f(6), \dots\}$
If we take $n = 3k$ in $\text{(1)}$ with $k \ge 0$, we can conclude that 
[note that $3$ divides $3$, ${(3k)}^2$, $3k$ and $63$]
$\tag 5 3 \text{ divides every number in } \{f(1), f(4), f(7), \dots\}$
If we take $n = 3k$ in $\text{(2)}$ with $k \ge 0$, we can conclude that 
[note that $3$ divides $9$, ${(3k)}^2$, $3k$ and $252$]
$\tag 6 3 \text{ divides every number in } \{f(2), f(5), f(8), \dots\}$
