Using induction to prove formula

Question

I am revising for my test from Discrete math. I have come to this problem.

I am to prove by using mathematical induction that

$6\times7^{n} - 2 \times 3^{n}$ is divisible by 4. for $n \ge 1$ ;

I created basic step :

$6\times7^{1} - 2\times3^{1} = 36 $

and induction step

$\forall n\ge 1, \exists K: 6\times7^{n} - 2\times3^{n} = 4K \Rightarrow \forall n \ge 1, \exists l: 6\times7^{n+1} - 2\times3^{n+1} = 4l$

we can transform the formula into

$6\times7\times7^{n} - 2\times3\times3^{n}$

which is basicly

$42\times7^{n} -6\times3^{n}$

But what is the next step? I can i prove this fact?

Answer 1

You can add to $4K$ the number $36\cdot 7^n-4\cdot 3^n$ which clearly is divisible by 4 and you get that $4K+36\cdot 7^n-4\cdot 3^n=6\cdot 7^{n+1}-2\cdot 3^{n+1}$

Answer 2

HINT:

$$\begin{align*} 6\cdot7^{n+1}-2\cdot3^{n+1}&=42\cdot7^n-6\cdot3^n\\ &=7(6\cdot7^n)-3(2\cdot3^n)\\ &=4(6\cdot7^n)+3(6\cdot7^n-2\cdot3^n) \end{align*}$$

Answer 3

If $6\cdot7^n-2\cdot3^n$ is divisible by 4, we can write it as $4k$ for some $k\in\Bbb N$.

Consider $24\cdot7^n$, which may be written as $4\cdot6\cdot7^n$ and is thus divisible by 4. Now add this to three times $6\cdot7^n-2\cdot3^n$: $$24\cdot7^n+3(6\cdot7^n-2\cdot3^n)=42\cdot7^n-6\cdot3^n$$ $$=6\cdot7^{n+1}-2\cdot3^{n+1}=4(6\cdot7^n+3k)$$ So 4 divides $6\cdot7^{n+1}-2\cdot3^{n+1}$ if 4 divides $6\cdot7^n-2\cdot3^n$, and the inductive step is shown.

Answer 4

First, show that this is true for $n=1$:

$6\cdot7^{1}-2\cdot3^{1}=4\cdot9$

Second, assume that this is true for $n$:

$6\cdot7^{n}-2\cdot3^{n}=4\cdot{k}$

Third, prove that this is true for $n+1$:

$6\cdot7^{n+1}-2\cdot3^{n+1}=$

$6\cdot7\cdot7^{n}-2\cdot3\cdot3^{n}=$

$7\cdot6\cdot7^{n}-3\cdot2\cdot3^{n}=$

$7\cdot6\cdot7^{n}-(7-4)\cdot2\cdot3^{n}=$

$7\cdot6\cdot7^{n}-7\cdot2\cdot3^{n}+4\cdot2\cdot3^{n}=$

$7\cdot(\color\red{6\cdot7^{n}-2\cdot3^{n}})+4\cdot2\cdot3^{n}=$

$7\cdot\color\red{4\cdot{k}}+4\cdot2\cdot3^{n}=$

$4\cdot(7\cdot{k}+2\cdot3^{n})$

---

Please note that the assumption is used only in the part marked red.

Answer 5

From your last step, you just need to replace $7^n$ by $\frac{4k+2.3^n}{6}$.

This gives $7[4k+2.3^n]-6.3^n=4[7k+2.3^n]$ which is divisible by $4$.