So, I've been revising for an exam and I came up against the question " prove $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$.
Now, I know how to do this. If I assume $n=k$ divisible by $7$, then I need to show that $n=k+1$ is divisible by $7$. The easiest way to do this is to state that if we label $n_k=k$ and $n_{k+1} = k+1$ then if $7|n_{k+1}-n_{k}$ and $7|n_{k} \Rightarrow 7|n_{k+1}$.
So, without further ado, $4(9^k)9 – 4(9) + 3(2^k)2 – 3(2^k) = 8\cdot4(9^k) + 3\cdot2^k = 8(4(9^k) + 3(2^k)) – 7\cdot 3(2^k)$. As required. Now clearly for $n=0$ this expression is $7$ so divisible for all $n\geq 0$.
My question is, how would I go about proving this via complete induction? I asked because "proof by strong induction also accepted" was mentioned in the mark scheme. Now according to wikipedia, my first assumption is that not only is $n=k$ true but so is $n=k-1$ and so on down to $n=0$. How do I improve my expression of that and how do I go from there to show a proof using this technique?
Edit: The build up to the question is on the topic of induction, so that's why I proved it that way, but Yuval Filmus has pointed out that if we are simply asked to prove it, the fact that $9 \equiv 2 \mod(7)$ means the proof is trivial.
Best Answer
One way you can use complete induction is to notice that
$$9^{n+1} - 1 = 8(1 + 9 + 9^2 + \dots + 9^n)$$
and
$$2^{n+1} - 1 = 1 + 2 + 2^2 + \dots + 2^n$$
Mutiply the first by $\displaystyle 4$ and second by $\displaystyle 3$ and add them up. Now, notice that $\displaystyle 32(9^k) + 3(2^k) = 28(9^k) + 4(9^k) + 3(2^k)$
If you assume $\displaystyle 4(9^k) + 3(2^k)$ is divisible by $\displaystyle 7$ for $k=0, 1, 2, \dots, n$, then the above shows that it is also true for $\displaystyle n+1$.