Is this form of finite induction correctly called "downward induction"

205 Views Asked by At

In a paper I'm writing, I have a lemma of the following form:

If $a_1, a_2, \dots, a_n$ is a sequence of type X and $a_n$ has property P, then $a_1, a_2, \dots, a_n$ all have property P.

As you might expect, this is proved by showing that if $a_k$ has property P, then so does $a_{k-1}$. What is the correct name or best description of the principle which allows us to conclude that the property holds whenever $k \leq n$?

I have said in the paper "By downwards induction, ...", but a reviewer has asked what "downwards induction" means. Although this term doesn't seem to be very widely used, it does seem to be somewhat established, and I don't know of a better term. Furthermore, it seems like the context makes it clear. Of course I could recast it as upward induction on $n-k$, but that does not seem like an improvement.

3

There are 3 best solutions below

2
On

It is called Fermat's Principle of Finite Descent

0
On

You could just rename $a_1, a_2,\ldots a_n$ to $a'_0, a'_1,a'_2 \ldots$ where $a'_k=a_{n-k}$ for $k<n$ and $a'_k=a_1$ else. Now it follows just by the ordinary induction.

0
On

I've always called it downwards induction. One possibility that might make the referee happy is to phrase it as:

Suppose that not all the $a_i$ have $P$ and let $k$ be maximal with $a_k$ not having $P$. Now blah, blah blah, a contradiction.

You might even at this point help out readers who do know the term by saying: Thus we have proved this by "downwards induction". The scare quotes might mollify the referee.