2

Is it possible to use induction twice or more in a proof? For instance, say we wished to prove the following proposition by induction:

Proposition

Suppose $x>3$ and $y<2$. Then $x^2 -2y>5$

Scratch Work

Let $P(x,y)$ be the inequality $x^2 -2y>5$. Let's choose a fixed integer $y$ that's less than 2, and from there prove by induction with first the bases-step showing $P(4,y)$ where $y$ is a fixed integer, followed by showing the inductive hypothesis is true.

After proving by induction $P(x,y)$ is true for all integers $x>3$ for a fixed integer $y$, we will once again use induction, but this time use induction to prove for all integers $y<2$, for a fixed integer $x>3$ that $P(x,y)$ is true. We then proceed with the standard inductive proof of showing the basis step is true and inductive hypothesis is true.

So, is it possible to use an inductive proof twice in a proof , kinda like this example? Moreover, is this particular example proof getting somewhere?

  • 1
    Is it possible to use induction twice or more in a proof? - Yes, but your specific proof is wrong regardless of that (and BTW, the question doesn't state that $x$ and $y$ are integers, so I would personally stay away from induction in this case). – barak manos Aug 29 '15 at 13:51
  • @barak manos Assuming x and y are integers, would it still be possible though to prove this proposition by induction? –  Aug 29 '15 at 13:57

1 Answers1

2

It is certainly possible to use induction more than once in a proof. Perhaps one of the more interesting applications of this idea is Cauchy induction.

To perform Cauchy induction, one first proves a base case, $P(1)$, and then proves $P(n)$ implies $P(2n)$. This inductively implies $P(2^n)$. Finally, you use decreasing induction, $P(n)$ implies $P(n-1)$, to show $P(n)$ for every natural number $n$.

Peter Woolfitt
  • 21,114