3
$\begingroup$

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.

  • 0
    Yes, or \cdot would have been even better. What you have written means 3.4, the decimal.2012-03-15

9 Answers 9

0

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$

6

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$.
  • 0
    @Belgi How else would you prove the statement, if $a=b$, then $a^n = b^n$, $\forall n \in \mathbb{N}$? In other words, how would you prove that $x^n$ is a well-defined function for all $n \in \mathbb{N}$? To prove any statement, holds true for all natural numbers, you need to use induction at some point or the other. Read Bill Dubuque's comment to TonyK's answer. It is just that in some cases, the induction is hidden deep under the layers.2012-07-04
5

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

4

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*}

  • 0
    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...2012-03-15
3

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)

3

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

  • 0
    Binomial Theorem at play. :-) +12012-03-17
1

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

  • 1
    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.2012-03-16
0

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$

0

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