Let $n ∈ N, n ≥ 1$. Prove that $4^n + 6n - 1$ is divisible by $9$. I've considered the equation by modulo 9 and tried the binomial theorem
$$4^n=(6-2)^n$$
but I still cannot prove it. Maybe there is a clever solution but so far I have been unable to spot it. Can anyone help me?
 A: Instead of $4^n=(6-2)^n$, you can try to use Binomial expansion on $4^n=(1+3)^n$. Then
$$ 4^n+6n-1=(1+3)^n+6n-1
=1+\binom{n}{1}3+\binom{n}{2}3^2+\cdots+\binom{n}{n}3^n+6n-1,$$
The resulting terms are exactly $9n+\binom{b}{2}3^2+\cdots+\binom{n}{n}3^n$, each of which is divisible by $9$.
A: $$ 4^3 = 64 \equiv 1 \ (mod \ 9)$$
So three cases:
1) n = 3k+1:
$$4^n+6n-1 \equiv 4+6(3k+1)-1 \equiv 4+6-1 \equiv 0 \ (mod \ 9)$$
2) n = 3k+2:
$$4^n+6n-1 \equiv 16+6(3k+2)-1 \equiv 7+12-1 \equiv 0 \ (mod \ 9)$$
3) n = 3k:
$$4^n+6n-1 \equiv 1+6(3k)-1 \equiv 0 \ (mod \ 9)$$
A: An inductive proof suits best here.
Say $P(n):4^n + 6n - 1$ is divisible by $9$.
Now for $n=1$,$$4^1+6\cdot 1-1=9$$ is divisible by $9$.
Hence $P(1)$ is true.
Let $P(k)$ be true for some $k \in \mathbb{N}, k>1$.
So, we have $$9\large|4^k + 6k - 1$$ or, $$4^k + 6k - 1=9m$$
For $n=k+1$, we have $$4^{k+1} + 6(k+1) - 1=4(4^k+6k-1)-18k+9$$ $$=4\cdot 9m -18k+9$$ $$=9(4m-2k+1)$$ which implies that $P(k+1)$ is true.
Hence $P(n)$ is true by induction. 
A: Hint: Let $u_n=4^n+6n-1$ then $u_{n+1}=4u_n-18n+9$ 
You will find that these expressions involving divisibility and powers are best tackled by induction or by finding a recurrence - there are various ways of framing the answer. Don't forget to prove a base case.
A: Modulo $9$, the sequence $6n$ goes $0, 6, 3, 0, 6, 3...$ The sequence $4^n$ goes $1, 4, 7, 1, 4, 7...$ Notice that both these sequences are $3$-periodic. Thus their sum is also $3$-periodic, and you can compute it explicitly to see that it goes $1, 1, 1, 1, 1...$.
