<s>[INST] 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$?
 [/INST] 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\}$
</s>