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

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