Cauchy’s Crazy Induction

Many people know about AM-GM inequality, we have that for any list of $n$ nonnegative real numbers $a_1, a_2, \ldots , a_n$ ,

$\sum_{k=1}^{n} a_k \geq n \sqrt[n]{\prod_{k=1}^{n}a_k}$

While reading about Arithmetic Mean-Geometric Mean Inequality’s proof at Wikipedia, I came across the reference to Augustin Louis Cauchy‘s original proof:

Cauchy, Augustin-Louis (1821). Cours d’analyse [source: https://archive.org/details/coursdanalysede00caucgoog ]

Here Cauchy used a crazy type of induction process, which can be stated as:

Step 1 : [The base case] Show that the statement is true for an integer .
Step 2: [The inductive step] This has two parts:

$P(k) \Rightarrow P(2k)$
$P(k) \Rightarrow P(k-1)$

Completing these two steps proves that the statement is true for all positive integers .

It has a very distinctive inductive step, and though it is rarely used, it is a perfect illustration of how flexible induction can be. The first part of the inductive step shows that the statement is true for larger and larger values of $n$ . But that leaves a lot of gaps in between. The second part ensures that all the gaps are taken care of.

I became curious to know about other instances when we can use this from of induction. So here are some other theorems which can be proved using Cauchy’s Crazy Induction (for proof refer to [2] given at end of this post):

1) Ky Fan inequality: If $x_i$ with $0 \leq x_i \leq \frac{1}{2}$ for $i = 1, \ldots, n$ are real numbers, then

$(\prod_{i=1}^n \frac{x_i}{1-x_i})^{1/n}\leq \frac{\frac{1}{n}\sum_{i=1}^n x_i}{1-\frac{1}{n}\sum_{i=1}^n x_i}$

2) Cauchy’s Inequality or Lagrange’s inequality : Let $n\geq 1$ and $x_1,\ldots, x_n,y_1, \ldots, y_n$ be a set of $2n$ real numbers. Then

$(\sum_{i=1}^n x_i y_i)^2 \leq (\sum_{i=1}^n x_i^2)(\sum_{i=1}^n y_i^2)$

References:

[1] Forward-backward induction, The Math Forum @ Drexel

[2] Francois Dubeau, “Cauchy and mathematical induction”, International Journal of Mathematical Education in Science and Technology 22 (1991), 965-969.

4 responses

mathsbyagirl on March 10, 2016 at 9:39 am said:

I love proof by induction; the satisfaction you get after completing a particularly challenging proof is unparalleled in my opinion!

LikeLiked by 1 person
- gaurish on March 10, 2016 at 11:25 am said:
  
  I love proof by contradiction. In words of G. H. Hardy:
  
  “Reductio ad absurdum, which Euclid loved so much, is one of a mathematician’s finest weapons. It is a far finer gambit than any chess play: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game. ”
  A Mathematician’s Apology (London 1941).
  
  LikeLiked by 1 person
  - mathsbyagirl on March 10, 2016 at 12:48 pm said:
    
    There are some brilliant quotes from that book.
    
    LikeLike
    - gaurish on March 10, 2016 at 12:55 pm said:
      
      Interestingly, mathematicians like Cédric Villani, Harold Edwards…. are living counterexamples of following G. H. Hardy’s quote:
      
      “There is no scorn more profound, or on the whole more justifiable, than that of the men who make for the men who explain. Exposition, criticism, appreciation, is work for second-rate minds. “
      
      LikeLiked by 1 person