Show that $\displaystyle{\frac{1}{9}(10^n+3 \cdot 4^n + 5)}$ is an integer for all $n \geq 1$ Show that $\displaystyle{\frac{1}{9}(10^n+3 \cdot 4^n + 5)}$ is an integer for all $n \geq 1$
Use proof by induction. I tried for $n=1$ and got $\frac{27}{9}=3$, but if I assume for $n$ and show it for $n+1$, I don't know what method to use. 
 A: Any proof will need to make use of induction at some point.


*

*Note that $10^n \equiv 1 \bmod 9$ and $4^n \equiv (1,4,7) \bmod 9$. (You need induction to prove previous statements.) Hence, $3 \times 4^n \equiv 3 \bmod 9$. Assimilating these together, we get that $$\left(10^n +  3 \times 4^n + 5 \right) \equiv (1 + 3 + 5) \bmod 9 = 0 \bmod 9.$$ Hence, $\displaystyle \frac{10^n + 3 \times 4^n + 5}{9}$ is an integer for all $n \in \mathbb{N}$.

*For a proof where induction is easily aparent, note that $$10^{n+1} + 3 \times 4^{n+1} + 5 = 10 \times \left( 10^{n} + 3 \times 4^{n} + 5 \right) - 9 \times \left( 4^n + 5 \right).$$
Hence,
$$\frac{10^{n+1} + 3 \times 4^{n+1} + 5}{9} = 10 \times \left( \frac{10^{n} + 3 \times 4^{n} + 5}{9} \right) - \left( 4^n + 5 \right).$$ Note that by induction hypothesis $\displaystyle \frac{10^{n} + 3 \times 4^{n} + 5}{9}$ is an integer and hence, $\displaystyle \frac{10^{n+1} + 3 \times 4^{n+1} + 5}{9}$ is also an integer since $4^n + 5$ is an integer for all $n$.

A: ${\displaystyle{\frac{1}{9}}(10^n+3 \cdot 4^n + 5)}$ is an integer for all $n \geq 1$
Proof by induction: 
For $n=1, {\displaystyle{\frac{1}{9}}(10^1+3 \cdot 4^1 + 5) = \frac{27}{9} = 3}$, so the result holds for $n=1$
Assume the result to be true for $n=m$, i.e.  $\displaystyle{\frac{1}{9}(10^m+3 \cdot 4^m + 5)}$ is an integer
To show ${\displaystyle{\frac{1}{9}}(10^{m+1}+3 \cdot 4^{m+1} + 5)}$ is an integer.
$$
\begin{align*}
\displaystyle{\frac{1}{9}(10^{m+1}+3 \cdot 4^{m+1} + 5) -(10^m+3 \cdot 4^m +5 )} &= \displaystyle{\frac{1}{9}\left((10^{m+1}-10^m) +3\cdot (4^{m+1}-4^m) \right)} \\
 &=\displaystyle{\frac{1}{9}\left[\left(10^m(10-1)+3 \cdot 4^m (4-1)  \right)\right]}\\
 &= \left(10^m+4^m\right)
\end{align*}
$$
which is an integer, and therefore ${\displaystyle{\frac{1}{9}}(10^{m+1}+3 \cdot 4^{m+1} + 5)}$ is an integer.
A: Here is a simple "direct proof":
\begin{align*}
10^n+3 \times 4^n + 5&=10^n-1 +3 \times 2^{2n}+6 =9999..9+6 \times [2^{2n-1}+1] \\
&=9999..9+6 \times (2+1)(2^{2n-2}-2^{2n-3}+\cdots-2+1) \\
&= 9 \times [1111...1+2 \times (2^{2n-2}-2^{2n-3}+\cdots-2+1)]
\end{align*}
A: Hint $\rm\ \ \forall\, n\ge 0\!:\ 9\ |\ f(n)\!\iff\! [\,9\ |\ f(0)\:$ and $\rm\:\forall\, n\ge 0\!:\ 9\ |\ f(n\!+\!1)\!-\!f(n)\,]\ \ $ (typical telescopy)
Now $\rm\, f(n) = 10^n\! +\! 3\cdot 4^n\! +\! 5\ \Rightarrow\ f(0)=9,\,$ and $\rm \ 9\:|\:f(n\!+\!1)\!-\!f(n) = (10\!-\!1)\, 10^n\! +\! 3\,(4\!-\!1)\, 4^n$
Note $\,\ $ The telescopy is trivial when viewed mod $9\!:\,$ it simply says that a function on $\mathbb N$ is constant if it never changes value 
$\rm\:\forall\,n\!:\,f(n\!+\!1)\equiv f(n)\Rightarrow\forall\,n\!:\,f(n)\equiv f(0)\:$  (trivially proved by induction)
A: Yet another "direct" method:
$$10^n=(1+9)^n=1+9k_1$$
$$4^n=(1+3)^n=1+3k_2$$Therefore $$10^n+3.4^n+5=9(1+k_1+k_2)$$
A: You don't need to use induction here. Just reduce everything modulo 9:  
$10 \equiv 1 \mod 9$, so $10^n \equiv 1 \mod 9$, so $10^n+5 \equiv 6 \mod 9$.  
To find the possible values of $4^n \mod 9$, note that $4^3 \equiv 1 \mod 9$, so $4^n$ must be $1, 4,$ or $7 \mod 9$. Thus $3 \cdot 4^n$ is equal to $3 \mod 9$.  
Hence $10^n + 3 \cdot 4^m + 5 \equiv 0 \mod 9$ for any positive integers $m, n$, not only when $n = m$.
A: This is the same as proving $(10^n +3⋅4^n +5)$  is divisible by 9. The rule for divisibility by $9$ is if it's digital sum is $9$, then it's divisible by $9$  
The sum of the three parts should give a digital sum of $9$.  
$10^n$ digital sum $=1$  
$4^n$ digital sum repeats in the cycle $(4,7,1)$
multiplying these by 3 gives the cycle$(12,21,3)$
The digital sum of $12,21,3$ are each $3$
$3\times4^n$ digital sum $=3$  
$5$ is last part  
$1 +3 +5 =9$ and is therefore divisible by $9$ 
A: $10^{0} +3⋅4^{0} +5=\color{red}{9}$ and $10^{n+1} +3⋅4^{n+1} +5=10^n +3⋅4^n +5+\color{red}{9}\cdot(10^n+4^n)$ for every $n\geqslant0$.
A: No induction necessary.
$$10 + 3\cdot 4^n + 5 \equiv 1 + 3\cdot 4^n + 5 \equiv 6 + 3\cdot 4^n \pmod9$$
Since everything including the base is divisible by three, this reduces to
$$6 + 3\cdot 4^n \pmod9 \iff 2 + 4^n \equiv 2 + 1 \equiv 0 \pmod3$$
