0

I was able to do it making the $10^n$ substitution ($10^{k+1} = 10^k (10)$). However, I cant prove it making the $3(4)^{k+2}$ substitution. It should definitely be possible, but I am stuck at $10^{k+1} + 4(9J) - 4(10^k) - 15$ (where J is an integer). I can continue on this path to factories out a $3$, but this is not a $9$. Any help?

user71207
  • 1,543

4 Answers4

1

Just reduce modulo $9$ : $$10^n + 3(4)^{n+2} + 5 \equiv 1^n + 3\times 16 \times 4^n + 5 \equiv 1+(3\times-2)\times4^n + 5 \equiv 6(1-4^n)$$

And $4^n = 1$ modulo $3$, so $1-4^n$ is dividible by $3$, so $6(1-4^n)$ is dividible by $9$.

TheSilverDoe
  • 29,720
0

If you want to prove this by induction, the induction step would be:

$$\begin{align} 10^{k+1} + 3(4)^{k+3} + 5 &= (9+1) \, 10^k + (3+1) \left[3(4)^{k+2} \right] + 5 \\ \\ &= 9 \left(10^k \right) + 9 \left( 4^{k+2} \right) + \left[ 10^k + 3(4)^{k+2} + 5 \right] \end{align}$$

A.J.
  • 3,892
  • How do you know the last [ .... ] part is divisible by 9? – user71207 Oct 22 '20 at 10:53
  • The part in the bracket is divisible by 9 by your induction assumption. – A.J. Oct 22 '20 at 11:06
  • Ahh I see. Were you attempting to get that or did it pop out by chance when you split 10 into (9+1) and 4 into (3+1)? – user71207 Oct 22 '20 at 11:18
  • Well, I'm not sure how to answer that; I suppose the primary goal was to get the expression in the induction step, but at the same time the remaining parts would have to be shown to be divisible by 9. – A.J. Oct 22 '20 at 11:32
0

You may apply the binomial formula to show the divisibility directly as follows:

\begin{eqnarray*} 10^n + 3(4)^{n+2} + 5 & = & (9+1)^n + 3(3+1)^{n+2} + 5 \\ & = & 9\cdot k + 1 + 9\cdot l + 3 + 5 \\ & = & 9(k+l) + 9 \end{eqnarray*}

trancelocation
  • 32,243
-1

Because $$10^n+3\cdot4^{n+2}+5=10^n-1+3\left(4^{n+2}-1\right)+9.$$ We see that $10^n-1$ is divisible by $9$ and $4^{n+2}-1$ is divisible by $3$.

The inductive step:

By the assumption of the induction we obtain: $$10^{n+1}+3\cdot4^{n+3}+5=10\left(10^n+3\cdot4^{n+2}+5\right)-18\cdot4^{n+2}-45$$ is divisible by $9$.

Michael Rozenberg
  • 194,933
  • What about the induction step let n = k+1? – user71207 Oct 22 '20 at 10:37
  • There's no need to do induction: that proves it for all $n$ in one step. – user3482749 Oct 22 '20 at 10:39
  • @user71207 I added something. See now. – Michael Rozenberg Oct 22 '20 at 10:40
  • Ah yep so thats when you sub in for $10^n$. But I was wondering how to do it but subbing in $3(4)^{n+2}$. Yes, it is a mathematical induction question – user71207 Oct 22 '20 at 10:43
  • @user71207 See my post. I showed it. – Michael Rozenberg Oct 22 '20 at 10:44
  • I can see that in the last step you did $10^{n+1}$ = $10^n (10)$, then you used the assumption of $10^n = ...$ from the first line – user71207 Oct 22 '20 at 10:49
  • @user71207 The assumption it's: $10^n+3\cdot4^{n+2}+5$ is divisible by $9$. We proved that $10^{n+1}+3\cdot4^{n+3}+5$ is divisible by $9$. I hope you checked that for $n=1$ the claim is true: $207$ is divisible by $9$. I think the proof without induction is better. See my first solution. – Michael Rozenberg Oct 22 '20 at 10:51
  • Yeah so $10^ + 3•4^{+2} + 5 = 9J$, where J is an integer. Rearanging to make $3 • 4^{n+2}$ the subject $3 • 4^{n+2} = 9J - 10^n - 5$. Then you sub this into the equation when n = k + 1. I'm having trouble proving this is divisible by 9 when this particular substitution is made – user71207 Oct 22 '20 at 10:56
  • @user71207 See please my post. I made it. what is not clear? Ask your questions. – Michael Rozenberg Oct 22 '20 at 10:58
  • I know your answer is correct. Sorry I'm just not really used to that setting out so I can't follow it. – user71207 Oct 22 '20 at 11:19