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