What is complete induction, by example? $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$

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

A simple 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)\:.\ $ Note $\rm\ S-9\ $ kills $\rm\ 9^n,\ $ and $\rm\ S-2\ $ kills $\rm\:2^n,\, $ therefore $\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 $\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.