Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

9 Answers 9

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$.
share|improve this answer
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... –  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
up vote 5 down vote accepted

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

share|improve this answer

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

share|improve this answer
1  
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)$$

share|improve this answer
    
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)

share|improve this answer

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

share|improve this answer
    
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
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. –  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$

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.