1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – barak manos Aug 29 '15 at 13:51
  • $\begingroup$ @barak manos Assuming x and y are integers, would it still be possible though to prove this proposition by induction? $\endgroup$ – user261954 Aug 29 '15 at 13:57
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy