Prove that $2^n + 5^n + 56$ is divisible by $9$, where $n$ is an odd integer 
Prove that $9 \mid2^n + 5^n + 56$ where n is odd

I have proved this by using division into cases based on the value of $n\bmod3$ but it seems a little bit clumsy to me and I wonder if there are other ways to prove it, probably by using modular arithmetic or induction? Below is my proof:
$\text{Case 1, }n\bmod3=0,\text{then $n=3k$ for some odd integer k:}$ $$\begin{align}
2^n+5^n+56 & =2^{3k}+5^{3k}+56
\\ & = 8^k+125^k+56
\\ & \equiv (-1)^k+(-1)^k+2\quad&\left(\bmod9\right)
\\ & \equiv 0\quad&\left(\bmod9\right)
\end{align}$$
$\text{Case 2, }n\bmod3=1,\text{then $n=3k+1$ for some even integer k:}$ $$\begin{align}
2^n+5^n+56 & =2^{3k+1}+5^{3k+1}+56
\\ & = 2\cdot8^k+5\cdot125^k+56
\\ & \equiv 2\cdot(-1)^k+5\cdot(-1)^k+2\quad&\left(\bmod9\right)
\\ & \equiv 9\equiv0\quad&\left(\bmod9\right)
\end{align}$$
$\text{Case 3, }n\bmod3=2,\text{then $n=3k+2$ for some odd integer k:}$ $$\begin{align}
2^n+5^n+56 & =2^{3k+2}+5^{3k+2}+56
\\ & = 4\cdot8^k+25\cdot125^k+56
\\ & \equiv 4\cdot(-1)^k+25\cdot(-1)^k+2\quad&\left(\bmod9\right)
\\ & \equiv -27\equiv0\quad&\left(\bmod9\right)
\end{align}$$
 A: Hint: $ $ let $\ \begin{align}n &= 2k\!+\!1\\ a&=(-2)^k\end{align}. $ $\bmod 9\,$ it's $\:\!f(a)\equiv\, 2a^2\!+\!5a\!+\!2\,\equiv 2\,(a\!-\!1)^2\equiv 0\,$ by $\, 3\mid a\!-\!1\!\!$
Or, conceptually $\,a\equiv 1\,$ is double root of $\,f(a)\,$ by  $\,f(1)\equiv 0\equiv f'(1)\,$ by $\,f'(a) \equiv 4a\!+\!5$
A: Here is a one-liner:
$$2^{2k+1}+5^{2k+1}+56\equiv2(1+3)^k+5(1+24)^k-7\equiv2(1+3k)+5(1+24k)-7\equiv126k$$
where we used binomial theorem in middle step.
A: It still involves cases, but here's a somewhat slicker proof.
By Euler's theorem, $a^{\varphi(n)}\equiv 1$ mod $n$, where $\varphi$ is Euler's totient function, which count the number of positive integers less than $n$ coprime to $n$.
As $\varphi(9)=6$, this implies that the residue of
$$2^n+5^n+56$$
mod $9$ depends only on $n$ mod $6$. If we assume $n$ is odd, then the only possible residues are $1,3,5$. As such it is sufficient to verify the claim for $n=1,3,5$.
We can further reduce the number of calculations we have to do by noting that $2$ and $5$ are multiplicative inverses mod $9$. Then, as $2^5\equiv 5$, we must have $5^5\equiv 2$, so the $n=5$ case follows from the $n=1$ case. Similarly, as $2^3\equiv -1$, we have $5^3\equiv -1$, letting us easily verify the $n=3$ case.
Though it is arguably simpler to just directly verify these three cases
A: Here's one way (not sure if it is the easiest, though).

Let us start with a lemma which you may easily prove by induction.
Lemma: For each natural number $k$, $2^{2k+1}+1$ and $2^{2k}-1$ are divisible by $3$.

Next, we have the following
Claim:
For $n=2k+1$, one has
$$2^n+5^n+56\equiv-2(2^{2k+1}+1)(2^{2k}-1)\mod 9.$$
In fact,
$$2^n+5^n+56\equiv 2^{2k+1}+(-2^2)^{2k+1}+2\equiv 2(2^{2k}-2\cdot 2^{4k}+1) \mod 9.$$
Observe that the RHS is equal to the RHS of the claim.

By the lemma, the RHS of the claim is divisible by $3\cdot 3=9$, hence the LHS as well.
A: 2 times complete induction only $n\rightarrow n+1$
$2^n+5^n+56=9\cdot m\Rightarrow$
$2^{n+2}+5^{n+2}+56=4\cdot 2^n+25\cdot 5^n+56=3\cdot 2^n+24\cdot 5^n+2^n+5^n+56=3\cdot 2^n+24\cdot 5^n+9\cdot m$
$3\cdot 2^n+24\cdot 5^n+9\cdot m=3(2^n+8\cdot 5^n)+9\cdot m$
$2^n+8\cdot 5^n=3\cdot x$, because $2^{n+1}+8\cdot 5^{n+1}=2^n+8\cdot 5^n+2^n+8\cdot 5^n+3\cdot 8\cdot 5^n=2\cdot 3x+3y  $
A: Mathematical induction approach
We know that $n$ is an odd integer, i.e. we can use $n= 2k - 1, k \in \mathbb{N}$. Hence, we can reformulate a starting statement:
$$9 \mid 2^{2k-1} + 5^{2k-1} + 56, \quad k \in \mathbb{N}.$$
$\text{1.}$ Basis of Induction:
For $\ k=1 \ $ we have:
$$\ 2^1 + 5^1 + 56 = 63 = 9 \cdot 7, \ $$
i.e. the statement is true for $\ k=1$.
$\text{2.}$ Induction Hypothesis:
Suppose the statement holds for some $\ k>1, \ $i.e. that it holds:
$$\ 2^{2k-1} + 5^{2k-1} + 56 = 9 \cdot m, \ m \in \mathbb{N}.$$
$\text{3.}$ The proof:
Let's check if the statement holds for $\ k+1. \ $ We have:
$2^{2(k+1)-1} + 5^{2(k+1)-1}+56 = 2^{2k+2-1} + 5^{2k+2-1}+56=4\cdot 2^{2k-1} + 25 \cdot 5^{2k-1} + 56 =
\\ 4\cdot (2^{2k-1}+5^{2k-1}+56) + 21\cdot 5^{2k-1} - 168 = 4\cdot 9 \cdot m + 21 \cdot (5^{2k-1} - 8).$
The first summand on the right side (i.e. $\ 4\cdot 9 \cdot m$) is obviously divisible by $\ 9, \ $ and because we know $\ 21 = 3 \cdot 7, \ $ it remains to prove that it holds: $\ 3 \mid 5^{2k-1} - 8, \ k \in \mathbb{N}.$ For that purpose we will use a mathematical induction too!
A: Write $a_n=2^n + 5^n + 56\cdot1^n$ and write $(x-2)(x-5)(x-1)=0$ as $x^3=8 x^2 - 17 x + 10$. Then
$$
a_{n+3} = 8 a_{n+2} -17 a_{n+1}+ 10 a_n
$$
Then $a_n \bmod 9$ is
$$
4,0,4,0,\color{red}{4,0,4},\dots
$$
Because of the linear recurrence, the sequence repeats as soon as it repeats three consecutive terms, $4,0,4$ in this case.
Bottom line $a_n \equiv 0 \bmod 9$ iff $n \equiv 1 \bmod 2$.
A: I wanted to offer a different approach, using a bit of algebra.
$$\begin{align}2^n+5^n+56 &\equiv \\  &\equiv2^n+5^n+54+2\\
&\equiv 2^n+5^n+2\\
 &\equiv 10^n-1+2^{2n}+2\times 2^n+1\\
&\equiv2^{2n}+2\times 2^n+1\\
&\equiv \left(2^n+1\right)^2\\
&\equiv 0\thinspace \thinspace \thinspace(\text{mod 9}) \end{align}$$
Because, $$\begin{align}2^n+1\equiv 0 \thinspace \thinspace \thinspace (\text{mod 3})\end{align}$$
where, $~n\equiv 1 \thinspace \thinspace \thinspace (\text{mod 2}).$
