Inductive proof of $\,9 \mathrel| 4^n+6n-1\,$ for all $\,n\in\Bbb N$

Prove that for all $n\in\mathbb N$, $9 \mathrel| (4^n+6n-1)$.

I have shown the base case if $n=0$ (which is a natural number for my course).

I'm now trying to prove that $9k=4^n+6n-1$.

I substituted $n+1$ for $n$, and have $4^{(n+1)}+6(n+1)-1$, which equals $4*4^n+6n+5$.

I'm stuck. Is that not the right way to go? I don't know how to get from the “$+5$” to “$-1$” so I can substitute $9k$ to the right side of the equation. Any help would be greatly appreciated.

Solution 1:

It's really simple this is how I'd approach it:

$4^{n+1}+6(n+1)-1=4(4^n+6n-1)-18n+9=4(4^n+6n-1)-9(2n-1)$

and since you've already proved that $4^n+6n-1=9k$ then you will have: $4(4^n+6n-1)-9(2n-1)=9k*4-9(2n-1)$

$=9(4k-(2n-1))$ and since $k$ and $2n-1$ are both integers then you can let $k'=4k-(2n-1)$ .

Now you'll have that $4^{n+1}+6(n+1)-1=9kk'$ which is a multiple of 9. So you can conclude for all natural numbers $n$ that $4^n+6n-1$ is divisible by $9$.

Solution 2:

hint $$4^{n+1}+6(n+1)-1=4\cdot4^n+6n+5=4(4^n+6n-1)-18n+9=$$ $$=4(4^n+6n-1)-9(2n-1)$$ first part is divisible to 9 by assumption and second part have 9 as factor

Solution 3:

Below we prove a more general result, because it requires little extra work yet yields great rewards, revealing structure that allows us to see the Binomial Theorem as the essence of the matter.

$\!\!\begin{align}\rm{\bf Theorem}\ \ \ \ \forall n\in\Bbb N\!:\ d\mid f(n) = a^n\! + bn + c &\rm \iff d\mid \color{blue}{(a\!-\!1)^2},\, \color{brown}{a\!+\!b\!-\!1},\, \color{darkorange}{1\!+\!c}\\ &\rm \iff d\mid f(0),\,f(1),\,f(2)\end{align}$

Proof $\ (\Leftarrow)\ $ By induction on $\rm\,n.\,$ The base case $\rm\,n=0\,$ claims that $\rm\, d\mid f(0)= \color{darkorange}{1\!+\!c},\,$ which is true by hypothesis. $ $ Next, assume that $\rm\,\color{#c00}{d\mid f(n)}\,$ as our inductive hypothesis.

Note $\rm\ \ \color{#0a0}{d\mid f(n\!+\!1)-f(n)}\, =\, a^n(a-1) + b\, =\, \color{blue}{(a^n\!-\!1)(a\!-\!1)}\, +\, \color{brown}{a\!+\!b\!-\!1}\ $ by hypotheses.

Thus $\rm\ \ \color{#0a0}{d\mid f(n\!+\!1)-f(n)}\ $ and $\rm\ \color{#c00}{d\mid f(n)}\ $ so $\rm\ d\,$ divides their sum $\rm\,f(n\!+\!1).$

$(\Rightarrow)\,\ \ \rm\, f(0)= \color{darkorange}{1\!+\!c},\,$ $\rm\ f(1)\!-\!f(0) = \color{brown}{a\!+\!b\!-\!1},\ $ $\rm f(2)\!-\!f(1)-(f(1)\!-\!f(0)) = (\color{blue}{a\!-\!1})^2\ \ $ QED

Specializing $\rm\ a,b,c,d = 4,6,-1,9\,$ yields the original problem:

$\rm\qquad\qquad\ 9\mid \color{blue}{(4\!-\!1)^2},\, \color{brown}{4\!+\!6\!-\!1},\,\color{darkorange}{1\!-\!1}\ \ \Rightarrow\ \ 9\mid f(n) = \color{blue}4^n\! + \color{brown}6n \color{darkorange}{-1},\ \ for\ all\,\ n\in\Bbb N$

The relationship with the Binomial Theorem ($\rm\color{#0a0}{BT}$) becomes obvious if we rewrite the theorem in arithmetical (equational) language, by replacing divisibility relations by equivalent congruences. Rearranging $\rm\ f(n) = a^n\! + b\,n + c\equiv 0\pmod d\, $ we have

$$\begin{eqnarray}\rm mod\ d\!:\ a^n \equiv \color{darkorange}{-c}+n(\color{brown}{-b}) &\equiv&\rm \color{darkorange}1 + n(\color{brown}{a\!-\!1})\quad by\ \ \color{brown}{{-}b\equiv a\!-\!1},\ \ \color{darkorange}{c\equiv -1}\\ \rm but\ \ \ \ a^n\equiv\, (1+a\!-\!1)^n&\rm\overset{\color{#0a0}{BT}}\equiv&\rm 1 + n(a\!-\!1) + \color{blue}{(a\!-\!1)^2}(\cdots)\ \ and\ \ \color{blue}{(a\!-\!1)^2}\equiv 0 \end{eqnarray}$$

Thus the result my be discovered by binomial expansion, then truncating higher powers of $\rm\,a\!-\!1.\,$ Hence the induction in the above proof is essentially a special case of the type of induction that is used to prove the first two terms of the Binomial Theorem. Indeed, one could rewrite the above proof to make this relationship more explicit. I leave that as an instructive exercise for the reader.

See also here for the slight generalization $\rm\, f(n) = e \,a^n+\cdots\,$ vs. $\,a^n+\cdots$

Generally as explained here, we deduce that $\rm\,f_n = f(n)\,$ satisfies a monic order $3$ recurrence $\,\rm (S-1)^2(S-a)\,f_n = 0\ $ so $\rm\ f_{n+3} = c_2\, f_{n+2} + c_1\, f_{n+1} + c_0\, f_n\,$ for $\rm \,c_i\in\Bbb Z,\,$ so a simple induction shows $\rm\,f_0,f_1,f_2\equiv 0\iff f_n\equiv 0\,\ \forall n\in \Bbb N,\,$ so the above proof may be viewed as a special case of the uniqueness theorem for recurrences. Thus $\ \rm d\mid f_0,f_1,f_2,\,\ldots\!\iff d\mid f_0,f_1,f_2,\,$ so $\,\rm \gcd(f_0,f_1,f_2,\ldots) = \gcd(f_0,f_1,f_2)$

Those who know a little ring theory may find it useful to view the universal essence of the matter as nothing but the Binomial Theorem in the ring of dual numbers $\rm\,R[x]/x^2.\,$ This ring proves handy when algebraically studying (higher) derivations, tangent/jet spaces, etc.

Solution 4:

HINT:

Let $\displaystyle f(n)=4^n+6n-1$

So, $\displaystyle f(m+1)-f(m)=4^m(4-1)+6=3(4^m-1)+9$

Using Why $a^n - b^n$ is divisible by $a-b$? $4^m-1$ is divisible by $4-1=3$

So, $\displaystyle f(m+1)-f(m)$ is divisible by $9$

$\displaystyle\implies f(m+1)$ will be divisible by $9$ if $\displaystyle f(m)$ is

Now, establish the base case i.e., for $n=1$

As to the origin of the problem,

for $n\in\mathbb N$, $\displaystyle4^n=(1+3)^n=\sum_{0\le r\le n}\binom nr3^r=1+3n+\sum_{2\le r\le n}\binom nr3^r$

Observe that the last part is divisible by $3^2=9$ as Proof that a Combination is an integer

So, $\displaystyle4^n=1+3n+9k$(where $k$ is an integer $\ge0$ )

or in congruence form $\displaystyle4^n\equiv1+3n\pmod9\ \ \ \ (1)$

This can be derived using induction as follows

If $\displaystyle4^m=1+3\cdot\underbrace m+9\cdot\underbrace u$ (where $u$ is an integer),

$\displaystyle\implies4^{m+1}=4\cdot4^m=(1+3)(1+3m+9u)=1+3\underbrace{(m+1)}+9\underbrace{(u+3u+m)} $

Now $\displaystyle6n-1$ actually compensates the constant and the coefficient of $n$ in $(1)$

More generally, we can prove $\displaystyle(1+a)^n\equiv1+na\pmod{a^2}$

In that case, the compensator will be $\displaystyle(a^2-a)n-1\pmod{a^2}$