Prove $\forall n\ge0,43\mid 6^{n+2}+7^{2n+1}$ in three ways

For an alternative method:

Let $a_n=6*{n+2}+7^{2n+1}=36\times 6^n+7\times 49^n$

Then, of course $a_0=36+7=43$ and $a_1=559=43\times 13$.

We remark that $6$, $49$ are roots of $$p(x)=(x-6)(x-49)=x^2 - 55 x + 294$$

Thus the $a_n$ satisfy the linear recurrence $$a_n=55a_{n-1}-294a_{n-2}$$

Since $a_0, a_1$ are both divisible by $43$ it follows from a trivial induction that all the $a_n$ are.

Note: we never needed the explicit form of the recursion, just that the sequence did satisfy a linear recursion over the integers.