Prove by induction that $ 4^{2n}-3^{2n}-7 $ is divisible by 84 for all natural numbers.

Question

Please, I have tried some methods of induction but I can't resolve. Sorry for my english.

I cannot complete to prove. I haved factoring, dividing, adding new terms but i cannot avance for the second step.

So,

$ 4^{2n}-3^{2n}-7 = 84t $

For induction, I have to prove this,

$ 4^{2(k+1)}-3^{2(k+1)}-7 = 84p $

Answer 1

Basis

$16-9-7=0$, which is divisible by 84.

Induction hypothesis

$84\Big|4^{2k}-3^{2k}-7$

Inductive step

$4^{2k+2}-3^{2k+2}-7$

$=16×4^{2k}-9×3^{2k}-7$

$=16(4^{2k}-3^{2k}-7)+7(3^{2k}+15)$

Now, the left bracket is divisible by 84 by hypothesis and right bracket is clearly divisible by 7×3, to prove that it is also divisible by 4, we write,

$3^{2k}+15=9^k-1^k+16$

Now, $(9-1)|9^k-1^k$ and also 8|16. So, it is divisible by 8, hence by 4.

Hope it helps

Answer 2

If $f(n)=4^{2n}-3^{2n}-7=16^n-9^n-7$

$$f(m+1)-9f(m)=16^m(16-9)-7(1-9)=7(16^m+8)=7(16^m-16+24)$$

will be divisible by $84$

if $16^m-16=16(16^{m-1}-1)$ is divisible by $12$

if $16^{m-1}-1$ is divisible by $3$ which is true as $16^{m-1}-1$ is divisible by $16-1$ for $m\ge1$

$\implies84|f(m+1)\iff84|9f(m)$

Now establish the base case $n=1$

Answer 3

Without induction:

$$F(n)=16^n-9^n-7=16(16^{n-1}-1)-9(9^{n-1}-1)$$

Clearly $F(n)$ is divisible by $3$ as $3|15|(16^{n-1}-1)$ for $n\ge1$

As $9^{n-1}-1$ is divisible by $9-1$ for $n\ge1,8|F(n)$

As $16^n-9^n$ is divisible by $16-9,7|F(n)$

So, $F(n)$ is divisible by lcm$(3,7,8)$

Generalization:

$G(n)=a^n-b^n-(a-b)$

is clearly divisible by $a-b=P$(say)

Again, $G(n)=a(a^{n-1}-1)-b(b^{n-1}-1)$

will divisible by $(a,b-1)=Q$(say) and $(b,a-1)=R$(say)

So, $G(n)$ will divisible by LCM$(P,Q,R)$

Answer 4

Another direct way uses the fact:

• $84 = 3 \cdot 4 \cdot 7$

So, just show divisibility by $\color{blue}{3,4,7}$:

• $4^{2n}-3^{2n}-7 = \color{blue}{(3+1)^{2n}} - 3^{2n} - 7 = \color{blue}{3\cdot k + 1} - 3^{2n} - 7 =\color{blue}{3}\cdot l$
• $4^{2n}-3^{2n}-7 = 4^{2n} - \color{blue}{(4-1)^{2n}} - 7 = 4^{2n} - (\color{blue}{4m + 1}) - 7 =\color{blue}{4}\cdot r$
• $4^{2n}-3^{2n}-7 = \color{blue}{(7-3)^{2n}} - 3^{2n} - 7 = \color{blue}{7s + 3^{2n}} - 3^{2n} - 7 =\color{blue}{7}\cdot t$