0

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.

Max
  • 386

3 Answers3

2

It is called Fermat's Principle of Finite Descent

happymath
  • 6,148
  • 2
    +1 but seems like a hundred dollar word for a 5 cent idea. – Guy Mar 14 '14 at 11:06
  • That may be a name for this principle, but a Google search indicates "finite descent" is even less used than "downward induction". It also seems less transparent to somebody who doesn't know the term. And according to this, the term is reserved for a contrapositive/negative version of the principle. – Max Mar 14 '14 at 11:11
1

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.

Jamie Radcliffe
  • 2,035
  • 1
  • 13
  • 8
0

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.

user2345215
  • 16,422