5
$\begingroup$

Say we have a property $P$ defined on the natural nubers. Usually students are taught that to pove $P(n)$ is true for all $n\in\mathbb N$ you have to do the following:

  • make a basis

and use either of the following arguments:

  • if $P(k)$ is true then $P(k+1)$ is true
  • if $P(n)$ is true $\forall n\leq k$ then $P(k+1)$ is true.

But you can also use slightly different methods. In particular I would like to look at a situation like this:

You prove that $P(k)\implies P(k+3)$ and combine this with three (or less) induction bases.

The (or less) part could be used, if something is only true for all numbers $2\bmod3$ for instance.

(The number $3$ can be any other natural number of course.)

I also asked this question here, on MSE, where it already has two answers (please check these first). However I thought this site would perhaps be more appropriate and thus lead to more response. So does anyone know problems that would be easier (less time consuming) to solve with a method like this than with the ordinary methods.

I think problems like these would be very nice examples to help students understand the power of induction.

$\endgroup$
5
  • $\begingroup$ I know I've seen instances where the strategy is prove $P(2k+1)$ then prove $P(k) \rightarrow P(2k)$. Just can't remember exactly what they were... $\endgroup$
    – Aeryk
    Nov 6, 2014 at 15:30
  • $\begingroup$ @Aeryk That would make a very nice answer. I hope you'll be able to recall an example... $\endgroup$
    – gebruiker
    Nov 6, 2014 at 15:37
  • $\begingroup$ Here's one (incomplete) example. Consider the $3n+1$ conjecture, and let $P(n)$ for positive $n$ be that a finite number of iterations will give a value below $n$. Then $P(K) \rightarrow P(2K)$ and $P(4k+1)$ is easy to prove. Unfortunately $P(4k+3)$ is an open problem. $\endgroup$
    – Aeryk
    Nov 6, 2014 at 15:46
  • $\begingroup$ Given a unit square, for which $n \in \mathbb{N}$ can you partition it into $n$ (not necessarily equal in area) squares? It turns out to be doable for $n = 1, 4,$ and all $n \geq 6$. Note that once you have a solution for $n = k$, you can take $1$ of the $k$ squares and subdivide it into $4$ squares in a $2 \times 2$ arrangement: This gives a total of $k - 1 + 4 = k + 3$ squares. So: Once you have constructions for $n = 6, 7, 8$, you can reason inductively (using the aforementioned strategy) to obtain all $n \geq 6$. $\endgroup$ Jan 5, 2015 at 22:40
  • $\begingroup$ Marginally related is the sci.logic thread Concerning simple induction that Bill Taylor started on 21 August 2006. Bill's post begins with this sentence: I have seen it written that sometimes, it is easier to prove a MORE informative sentence than a less informative one, by indutction. $\endgroup$ Jan 8, 2015 at 16:30

2 Answers 2

3
$\begingroup$

The first time I worked through Cauchy's proof of the AM-GM inequality I had to stop myself from shouting out loud: THIS IS OUTRAGEOUS! Less time consuming I don't know, but easier (in the sense of more intuitive) for me, yes.

I first came across the problem in Spivak's excellent book Calculus (Chapter 2, Problem 22.)

Theorem

Let $a_{1},\ldots,a_{n}$ be a set of real numbers such that $a_{i}\geq 0$ for each $i.$

Define $$ \begin{align*} A_{n} & = \frac{a_{1} + \ldots + a_{n}}{n} \\ G_{n} & = \left[a_{1}\ldots a_{n}\right]^{\frac{1}{n}} \end{align*} $$

Then $A_{n} \geq G_{n}.$

Proof

We use induction on the set of integers $2^{k}$ for $k \in \mathbb{N}.$

For the case $k=1,$ we need to show $\frac{a_{1}+a_{2}}{2} \geq \sqrt{a_{1}a_{2}},$ which is done by considering the fact that $(\sqrt{a_{1}}-\sqrt{a_{2}})^{2} \geq 0.$

Assume the proposition holds for $2^{k}.$ For $2^{k+1}$ we have $$ \begin{align*} A_{2^{k+1}} & = \frac{a_{1} + \ldots + a_{2^{k}} + a_{2^{k}+1} + \ldots + a_{2^{k+1}}}{2^{k+1}} \\ & = \frac{1}{2} \left[ \frac{a_{1} + \ldots + a_{2^{k}} } {2^{k}} + \frac{ a_{2^{k}+1} + \ldots + a_{2^{k+1}}}{2^{k}} \right] \\ & = \frac{1}{2}\left[ A + B \right] \\ & \geq \sqrt{AB} \\ & \geq [(a_{1}\ldots a_{2^{k}})^{\frac{1}{2^{k}}}( a_{2^{k}+1}\ldots a_{2^{k+1}})^{\frac{1}{2^{k}}}]^{\frac{1}{2}} & \text{(by inductive hypothesis)}\\ & = G_{2^{k+1}} \end{align*}$$

(Note we have even used the base step here!)

Now we go back and think about general $n.$ Let $m$ be defined so that $2^{m} > n$ and let $a_{n+1}=\ldots=a_{2^{m}} = A_{n}.$ Then $$ A_{2^{m}} = \frac{a_{1} + \ldots + a_{n} + (2^{m}-n)A_{n}}{2^{m}} = A_{n} $$ so that $$ (A_{n})^{2^{m}} \geq a_{1}\ldots a_{n}(A_{n})^{2^{m}-n} $$ and rearranging easily proves the theorem.

There are certainly a few details missing here which you would have to fill out, and perhaps this article is a bit clearer (a less slick proof), but the proof can definitely be broken down so that undergraduates can work through it as an exercise in several steps.

Edit: The reason I find this proof so appealing is that the step $P(2^{k}) \Rightarrow P(2^{k+1})$ is really reduced to basic algebra, whereas $P(n) \Rightarrow P(n+1)$ requires more lemmas. My conceptual focus when reading this proof is on the idea of using a different induction step and how this simplifies the argument so much. In this sense, I find Cauchy's proof easier and more understandable even if it is not faster than others.

$\endgroup$
1
$\begingroup$

For example: to prove that $8|n^2-1$ for odd numbers $n$, we can go about like this:

  • $8|1^2-1=0$
  • Suppose $8|k^2-1$, for an odd $k$

Now we have \begin{align}(k+2)^2-1=&k^2+4k+4-1\\=&k^2-1+4(k+1)\end{align} which concludes our proof since $k+1$ is even by assumtion.


This is my own very poor example, which saves you about a few seconds. I'm sure others will provide much more usefull contributions.

$\endgroup$
1
  • $\begingroup$ Of course, in this case $n$ odd means we can write it as $2k+1$. Then $n^2 - 1 = 4k^2 + 4k + 1 - 1 = 4k(k+1)$; note that $k(k+1)$ must be divisible by $2$, so $4k(k+1)$ is divisible by $8$ as desired. QED Alternatively, $n$ odd means among its predecessor and successor, one is $2 \mod 4$ and the other is $0 \mod 4$; therefore, their product $(n-1)(n+1) = n^2 - 1$ is divisible by $8$ as desired. QED $\endgroup$ Jan 6, 2015 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.