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.

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

2 Answers 2

7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks, that is actually much less painful than I was expecting! :D $\endgroup$
    – user892
    Jan 10, 2011 at 21:47
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I had to re-read that a few times, but wow, that's fantastic, +2 if I could. $\endgroup$
    – user892
    Jan 11, 2011 at 0:26
  • $\begingroup$ What is $S$ in this case? $\endgroup$ Jul 27, 2016 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy