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
 A: 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$$
A: $\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}$
A: 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$.
A: 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.
A: 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.
A: 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!
