2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Arthur Sep 15 '17 at 10:19
  • $\begingroup$ What is k? Please elaborate $\endgroup$ – neonpokharkar Sep 15 '17 at 10:19
  • $\begingroup$ Ur series might have negative terms $\endgroup$ – neonpokharkar Sep 15 '17 at 10:21
  • $\begingroup$ It evaluates to $2-4^n$ $\endgroup$ – neonpokharkar Sep 15 '17 at 10:22
  • $\begingroup$ it is actually 4^(n+1) and how do you write the mathematical equation like that ? $\endgroup$ – Anas Sbouria Sep 15 '17 at 10:23
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

$\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}$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.