<s>[INST] Proof by induction that $3^{4n + 1} + 5^{2n + 1}$ is divisble by $8$ This is a homework problem:

Prove that: $$ 3^{4n+1} + 5^{2n+1}$$ is divisible by $8$ for every natural number $n$.

Base case: $$n = 0$$
$$ 3^{0 + 1} + 5^{0 + 1} = 8$$
$$8\bmod8 = 0 $$ Base case verified.
Inductive Hypothesis: Assume for some $n$, $$ 3^{4n+1} + 5^{2n+1} =8k$$ where $k$ is any non-negative integer.
Prove that: $$ 3^{4(n+1)+1} + 5^{2(n+1)+1} =8l$$
Indeed: $$ 3^{4n+4+1} + 5^{2n+2+1} = 3^4\cdot3^{4n+1} + 5^2\cdot5^{2n+1}$$
$$ = 81\cdot3^{4n+1} + 25\cdot5^{2n+1} $$
$$ = (80+1)\cdot3^{4n+1} + (24+1)\cdot5^{2n+1} $$
$$ = 80\cdot3^{4n+1} + 24\cdot5^{2n+1} + 3^{4n+1} + 5^{2n+1} $$
$$ = 8(10\cdot3^{4n+1} + 3\cdot5^{2n+1}) + 8k $$
$$ = 8(10\cdot3^{4n+1} + 3\cdot5^{2n+1} + k) $$
Is this wrong in any particular way? My answer is different from the textbook, but I feel like I sufficiently proved that $ 3^{4(n+1)+1} + 5^{2(n+1)+1} =8l$.
Edit: What the book did:
$$ = 81\cdot3^{4n+1} + 25\cdot5^{2n+1} $$
$$ = (56+25)\cdot3^{4n+1} + 25\cdot5^{2n+1} $$
$$ = 56\cdot3^{4n+1}+25\cdot3^{4n+1} + 25\cdot5^{2n+1} $$
$$ = 56\cdot3^{4n+1}+25(3^{4n+1} + 5^{2n+1}) $$
$$ = 56\cdot3^{4n+1}+25(8k) $$
$$ = 8(7\cdot3^{4n+1}+25k) $$
 [/INST] Your method looks fine.  Another method that is slightly cleaner: Let $S_n=3^{4n+1}+5^{2n+1}=3\cdot 81^n+5\cdot25^n$.  Note that $S_n$ satisfies $$ S_n=106S_{n-1}-2025S_{n-2} $$
(This can be found by that fact that $u_n:=c_1A^n+c_2B^n$ satisfies the recursion $u_n=(A+B)u_{n-1}-ABu_{n-2}$)
This recursion implies that if $k|S_{n}$ and $k|S_{n+1}$ then $k|S_{n+2}$.  Since the initial values of $S_n$ are $S_0=8$ and $S_1=368$, we can see inductively that $8|S_n$ for all $n\in\Bbb N_0$.
</s>