14
$\begingroup$

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.

  • 2
    Someone should note that the proof is immediate if we're allowed to use the basic fact that $9 \equiv 2 \pmod{7}$.2011-01-11

2 Answers 2

7

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

  • 0
    Thanks, that is actually much less painful than I was expecting! :D2011-01-10
4

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.

  • 0
    What is $S$ in this case?2016-07-27