# A sequence divisible by 9

I was trying to solve this series by mathematical induction for every $n$ from $\Bbb N$ : $u_n=n4^{n+1}-(n+1)4^n+1$ is divisible by $9$.

The initiation was pretty easy, but I only managed to prove $u_{n+1}=3k$ while $k$ is an integer and I don't think if it's divisible by $3$ implies that it is divisible by $9$ ; is it ? if not how can I proceed to prove the divisibility ? by mod maybe? thanks in advance for your answer

• I edited your post. Could you please check that I haven't introduced any mistakes. As to your last question, $3$ is divisible by $3$, but not by $9$, so something which is divisible by $3$ is not necessarily divisible by $9$. – Arthur Sep 15 '17 at 10:19
• What is k? Please elaborate – neonpokharkar Sep 15 '17 at 10:19
• Ur series might have negative terms – neonpokharkar Sep 15 '17 at 10:21
• It evaluates to $2-4^n$ – neonpokharkar Sep 15 '17 at 10:22
• it is actually 4^(n+1) and how do you write the mathematical equation like that ? – Anas Sbouria Sep 15 '17 at 10:23

For integer $n\ge0,$ using Binomial Expansion

$$4^m=(1+3)^m\equiv1+3m\pmod9$$

$$\implies u_n=n4^{n+1}-(n+1)4^n+1$$

$$\equiv n\{1+3(n+1)\}-(n+1)(1+3n)+1\pmod9$$

$$\equiv4n+3n^2-(4n+1+3n^2)+1\equiv0$$

\begin{align}{\bf Hint}\quad\ u_n = &\ (1-3n)(1+3)^n-\,1\\ {\rm but}\ \ \ &\ (1-na)\color{#0a0}{(1+a)^n}-\,1\\ \equiv\ &\ (1-na)(\color{#0a0}{1+na})- 1\equiv 0\!\!\!\pmod{\color{#c00}{a^2}}\ \ {\rm by\ \color{#0a0}{Binomial\ Theorem}} \end{align}

Remark  If you must use induction then you can substitute the simple inductive proof below of the first two terms of the Binomial Theorem.

\!\begin{align}{\rm mod}\,\ \color{#c00}{a^2}\!:\,\ \color{#0a0}{(1+ a)^n}\, \ \ \equiv&\,\ \ \color{#0a0}{1 + na}\qquad\qquad\ \ \ {\rm i.e.}\ \ P(n)\\[1pt] \Rightarrow\ (1+a)^{\color{}{n+1}}\! \equiv &\ (1+na)(1 + a)\\[2pt] \equiv &\,\ \ 1+ na+a+n\color{#c00}{a^2}\\ \equiv &\,\ \ 1\!+\! (n\!+\!1)a\qquad\quad {\rm i.e.}\ \ P(\color{}{n\!+\!1})\\ \end{align}

Base case: $1\cdot 4^2 - 2\cdot 4^1 + 1 = 9$ is divisible by $9$.

Induction step: Assume it is true for $n = a$, say $u_a = 9k$. Now to see what we get for $n = a+1$: $$u_{a+1} = (a+1)4^{a+2} - (a+2)4^{a+1} + 1\\ = a4^{a+2} + 4^{a+2} - (a+1)4^{a+1} - 4^{a+1} + 1\\ = 4(a 4^{a+1} - (a+1)4^a + 1) + 4^{a+2} - 4^{a-1} - 3\\ = 4\cdot 9k + 3\cdot 4^{a+1} - 3$$ Now what remains is showing that $3\cdot 4^{a+1} - 3$ is divisible by $9$. This can be done by induction exactly like for $u_n$, only this time it's easier. We can also show this directly by using the binomial theorem to expand $4^{a+1} = (3+1)^{a+1}$. We see that $$3(3+1)^{a+1} - 3= 3(3^{a+1} + (a+1)\cdot 3^a + \cdots + (a+1)\cdot 3 + 1) - 3\\ = 3^{a+2} + (a+1)\cdot 3^{a+1} + \cdots + (a+1)\cdot 3^2 + 3 - 3\\ = 9(3^{a} + (a+1)\cdot 3^{a-1} + \cdots + (a+1))$$which is divisible by $9$.

Ur series can be written as, $$a_n=(3n-1)4^n+1$$ At $n=1$, $$a_1=9=\text{divisible by 9}$$ Suppose, $$a_n=(3n-1)4^n+1=9k$$ Then, $$a_{n+1}=(3n+2)4^{n+1}+1$$$$=4(3n+3-1)4^n+1$$$$=4(3n-1)4^n+3×4^{n+1}+4-3$$$$=4((3n-1)4^n+1)+3(4^{n+1}-1)$$

For series $b_n=4^n-1$ At $n=1$, $$b_1=3$$ Suppose, $$b_n=4^n-1=3g$$ Then, $$b_{n+1}=4^{n+1}-1$$$$=(4^n-1)(4^n+1)$$$$=3g(4^n+1)$$ There fore by induction $4^n-1=3m$

\begin{align}=4×9 k+3×3m\\=9(4k+m)\end{align} Therefore $a_n$ is divisible by 9.

Since $4\equiv1(\mod3)$, we obtain: $$n4^{n+1}-(n+1)4^n+1=3n4^n-4^n+1=$$ $$=3n4^n-3n-(4^n-1)+3n=(4^n-1)(3n-1)+3n=$$ $$=3(3n-1)\left(4^{n-1}+...+1\right)+3n\equiv3(3n-1)n+3n=9n^2$$ and we are done!

Let $v_n= u_n-1=-1 \cdot 4^n + 3n \cdot 4^n$. This implies that $v_n$ satisfies a second-order linear recurrence given by expanding $(x-4)^2$: $$v_n = 8v_{n-1} - 16v_{n-2}$$ This gives a recurrence for $u_n=v_n+1$: $$u_n = 8(u_{n-1}-1) - 16(u_{n-2}-1)+1 = 8u_{n-1} - 16u_{n-2} + 9$$ Therefore, if $9$ divides $u_{n-1}$ and $u_{n-2}$, then $9$ divides $u_n$. Since $9$ divides $u_0=0$ and $u_1=9$, we're done.