# 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.

-
At first I thought you meant the decimal $3.4^n$, i.e. $(3 + (4/10))^n$. Then I saw that your proposed statement could not be true in that case, and wondered whether it should be $\left(3.\overline{4}\right)^n$ (with a bar over the $4$, indicating that it repeats, i.e. $(3.44444444\ldots)^n$) which is $3+(4/9)$. But apparently you meant $3\cdot4^n$. – Michael Hardy Mar 15 '12 at 21:02
Should I have used \times in latex instead – Kirthi Raman Mar 15 '12 at 21:05
Yes, or \cdot would have been even better. What you have written means 3.4, the decimal. – user22805 Mar 15 '12 at 21:20

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$.
-
These statements can be proven without induction. $10^n \equiv 1 \bmod 9$ because 9 divides $10^n-1=9999...9$. The second one $3 \times 4^n \equiv 3 \bmod 9$ is "obvious" because $3 \times 4^n -3 =3(4^n-1)=3 \times (4-1) \times (4^{n-1}+...+4+1)$ is a multiple of 9... – N. S. Mar 15 '12 at 21:11
@N.S. Any statement which you want to prove for all natural numbers requires induction (perhaps hidden) at some point. Your $\ldots$ in writing $9999\ldots99$ is where the induction lies in your first argument, while your "obvious" claim that $4^n-1 = (4-1) \times (4^{n-1} + 4^{n-2} + \cdots + 4 + 1)$ again involves induction. – user17762 Mar 15 '12 at 21:13
@Sivaram: You really don't need induction here. See my answer. – TonyK Mar 15 '12 at 22:19
@TonyK Actually he is right, you do. How do you prove that $a \equiv b \mod m$ implies that $a^n \equiv b^n \mod m$? You used induction to prove that.... – N. S. Mar 15 '12 at 23:08
@N.S. - you make look at $a,b$ as elements of $\mathbb{Z}_m$ and use the fact that if $a=b$ then $a^n=b^n$ – Belgi Jul 4 '12 at 4:57

${\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*}

-
Problem is simpler than doing this. – Saeed Mar 15 '12 at 21:28
I like this way more than induction. It is more quick. – Beni Bogosel Mar 15 '12 at 22:32
If I had to solve it myself I would use mod 9 arithmetic, that's simpler. I like this solution only because it can be explained to a secondary school student... – N. S. Mar 15 '12 at 23:12

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)$$

-
Binomial Theorem at play. :-) +1 – user21436 Mar 17 '12 at 7:26

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)

-

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$.

-
Alternatively by the binomial theorem $4^n=(1+3)^n=1^n+\cdots$ where the "$\cdots$" terms all include factors of $3$ and so disappear when we multiply the whole with $3$, so $3\cdot 4^n\equiv 3\cdot 1^n\equiv 3 \pmod 9$. – Henning Makholm Mar 15 '12 at 23:35
But you do use induction to prove that $1^n \equiv 1$. Simply because the induction is trivial does not imply that it's not an induction. In fact one very successful strategy for inductive proofs is to transform them so that the induction becomes trivial - which I stress in some of my prior posts here. – Bill Dubuque Mar 16 '12 at 1:46

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$.

-

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$$

-