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.
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.
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$
Any proof will need to make use of induction at some point.
${\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.
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*}
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)
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)$
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$.
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$
$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$.