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

Question

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 induction bases.

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

Now I know this is valid. I was just wondering if anyone knows any problems that would be easier (less time consuming) to solve with a method like this than with the ordinary methods.

Answer 1

Try to prove that $12|(k^4 - k^2)$ for every natural number $k$. It can be checked to be true for $k \in \{1,2,3,4,5,6\}$. The induction step $12 | (k^4 - k^2) \implies 12 |((k+6)^4 - (k+6)^2)$ is easy (if not tedious) to verify.

Answer 2

There are certainly some situations where it is more natural to use the method you mentioned, for example, when trying to prove $$ n+(n-2)+(n-4)+\dots=n^2+\frac{n}2+\frac{(-1)^n}{2}n, $$ where the above sum is only over positive integers. The proof is still pretty short using strong induction, it would only be a couple of words longer.