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
    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$.2012-03-15
  • 0
    Should I have used \times in latex instead2012-03-15
  • 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$.
  • 1
    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...2012-03-15
  • 0
    @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.2012-03-15
  • 0
    @Sivaram: You really don't need induction here. See my answer.2012-03-15
  • 0
    @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....2012-03-15
  • 0
    @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$2012-07-04
  • 0
    @Belgi To prove the fact that if $a=b$, then $a^n = b^n$, you need induction.2012-07-04
  • 0
    @Marvis - you don't, they ($a,b$)$ are the same element.2012-07-04
  • 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*}

  • 1
    Problem is simpler than doing this.2012-03-15
  • 0
    I like this way more than induction. It is more quick.2012-03-15
  • 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$.

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