# On problems which can be proved easier if we use a different induction step

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.

• 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... – Aeryk Nov 6 '14 at 15:30
• @Aeryk That would make a very nice answer. I hope you'll be able to recall an example... – gebruiker Nov 6 '14 at 15:37
• 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. – Aeryk Nov 6 '14 at 15:46
• 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$. – Benjamin Dickman Jan 5 '15 at 22:40
• 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. – Dave L Renfro Jan 8 '15 at 16:30

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.

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.

• 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 – Benjamin Dickman Jan 6 '15 at 8:03