# What is complete induction, by example?

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.

-
A proof by induction is also a proof by complete induction. –  Rasmus Jan 10 '11 at 21:31
See my answer in math.stackexchange.com/questions/14984/… –  Arturo Magidin Jan 10 '11 at 21:35
@Arturo Wow, thanks, might take me a while to digest that... –  Ninefingers Jan 10 '11 at 21:46
Be sure to ask questions if you have any. The answer does not address how to specifically apply it to this particular problem, though. –  Arturo Magidin Jan 10 '11 at 21:47
Someone should note that the proof is immediate if we're allowed to use the basic fact that $9 \equiv 2 \pmod{7}$. –  Yuval Filmus Jan 11 '11 at 0:36

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

-
Thanks, that is actually much less painful than I was expecting! :D –  Ninefingers Jan 10 '11 at 21:47

A simple but powerful way to prove by complete induction that $\rm\ f(n) = 4\cdot 9^n + 3\cdot 2^n \equiv 0\ \ (mod\ 7)\:$ is as follows: Put $\rm\ S\ f(n) = f(n+1)\:.\$ Since $\rm\ S-9\$ kills $\rm\ 9^n,\$ and $\rm\ S-2\$ kills $\rm\:2^n\:,\$ we see that $\rm (S-9)\ (S-2)\$ kills $\rm\:f(n)\:,\$ i.e. $\rm\ f(n)\$ satisfies $\rm\ f(n+2) - 11\ f(n+1) + 18\ f(n) = 0\:.\$ Now since $\rm\ 0\equiv f(0)\equiv f(1)\:,\:$ using the recurrence and complete induction shows that $\rm\ f(n)\equiv 0\$ for all $\rm\ n \in \mathbb N$.

An analogous complete induction proves that a solution of a monic linear recurrence is determined uniquely by its initial conditions - the uniqueness theorem for linear difference equations. Generally uniqueness theorems provide very powerful tools for proving equalities. See some of my other posts for further examples of such.

This is closely related to inductive proofs of the recursion theorem, which justifies the use of recursive definitions. For a nice introduction see Henkin: On mathematical induction.

-
I had to re-read that a few times, but wow, that's fantastic, +2 if I could. –  Ninefingers Jan 11 '11 at 0:26