2
$\begingroup$

Mathematical induction is the proof method that shows the truth of $\forall n\in\mathbb N:P(n)$ by establishing these two things:

  1. Base case: $E(0)$,
  2. Inductive step: $\forall n\in\mathbb N:P(n)\implies P(n+1).$

My question is:

Is there a mathematical proof by induction that establishes the inductive step itself by mathematical induction? I.e. establishing $\forall n\in\mathbb N:P(n)\implies P(n+1)$ by showing that:

  1. $P(0)\implies P(1)$,
  2. $\forall n\in\mathbb N:(P(n)\implies P(n+1))\implies (P(n+1)\implies P(n+2))$

If there are such proofs, are they just artificial or do they occur in praxis?

$\endgroup$
  • $\begingroup$ Here: math.stackexchange.com/questions/2332127/… $\endgroup$ – Cauchy Jul 8 '17 at 17:12
  • $\begingroup$ @Cauchy: Could you comment on how the question you linked to has something to do with my question? Thanks :-) $\endgroup$ – user7280899 Jul 8 '17 at 17:14
  • 1
    $\begingroup$ In my thesis I at some point had a proof of something that was built as an induction on the length of some iteration, then the complexity of a formula, then on the rank of the objects appearing in the formula. I was quite happy when it turned out that the theorem was unnecessary. $\endgroup$ – Asaf Karagila Jul 8 '17 at 17:36
  • 4
    $\begingroup$ $(P(n) \Rightarrow P(n+1)) \Rightarrow (P(n+1) \Rightarrow P(n+2))$ is equivalent to $P(n+1) \Rightarrow P(n+2)$, which means that assuming $P(n) \Rightarrow P(n+1)$ doesn't really help. $\endgroup$ – Fabio Somenzi Jul 8 '17 at 18:47
  • 1
    $\begingroup$ You also need to show $P(0)$ is true. $\endgroup$ – Shuri2060 Jul 8 '17 at 19:25
4
$\begingroup$

There isn't any "natural" one. Indeed given formulas $A,B,C$, $(A\to B)\to (B\to C)$ is equivalent to $\neg (\neg A\lor B) \lor (\neg B\lor C)$ which in turn is equivalent to $(A\land \neg B)\lor (\neg B\lor C)$, distributing over the middle $\lor$ this gives $(A\lor \neg B\lor C)\land (\neg B\lor \neg B\lor C)$ and then noting that $\neg B\lor C$ implies $A\lor \neg B\lor C$ we see that this last formula is equivalent to $\neg B\lor C$, that is $B\to C$.

According to the completeness theorem for propositional logic, this equivalence $(A\to B)\to (B\to C) \cong (B\to C)$ can be proved, and so in particular if you have a proof of $(P(n)\to P(n+1))\to (P(n+1)\to P(n+2))$, you have a proof of $P(n+1)\to P(n+2)$.

Therefore if you know how to prove $P(0)$ and $P(0)\to P(1)$ and $\forall n, (P(n)\to P(n+1))\to (P(n+1)\to P(n+2))$, you know how to prove $P(0), P(1)$ and $\forall n\geq 1, P(n)\to P(n+1)$ using only basic properties of integers and no induction (only $n\geq 1\to \exists m, m+1= n$).Then with induction you can derive $\forall n, P(n)$.

So there is no "natural proof" that uses this scheme, although as the other answers show, it's not rare to use another induction in the induction step.

$\endgroup$
  • $\begingroup$ I think strictly speaking the answer should be "no", since $P(n+1) \to P(n+2)$ isn't equivalent to $P(n) \to P(n+1)$. In a theorem that holds in every case except $n=1$, his formulation would allow for an invalid proof. $\endgroup$ – DanielV Jul 11 '17 at 19:04
  • $\begingroup$ No it wouldn't, if OP had a proof of the kind he's referring to, that would always be a valid proof, using induction on the formula $Q(n) = P(n) \to P(n+1)$. Unless I don't see your point $\endgroup$ – Max Jul 11 '17 at 19:08
  • $\begingroup$ Well the general point is that you need to establish both $P(0)$ and $P(1)$ for the induction step $n+1 \mapsto n+2$ to cover everything else. $\endgroup$ – DanielV Jul 11 '17 at 21:28
  • 1
    $\begingroup$ No but what OP does is prove $(P(n)\to P(n+1))\to (P(n+1)\to P(n+2))$ for all $n$ and $P(0)\to P(1)$. By induction, this establishes $P(n)\to P(n+1)$ for all $n$. Then OP uses "regular" induction to proceed. What I show in my answer is that the step "By induction, this establishes $P(n)\to P(n+1)$" can be replaced by "This establishes $P(n+1)\to P(n+2)$" and since both base cases $P(0)$ and $P(1)$ have been established ($P(1)$ follows from $P(0)0$ and $P(0)\to P(1)$), this is sufficient $\endgroup$ – Max Jul 11 '17 at 22:04
2
$\begingroup$

$(P(n)⇒P(n+1))⇒(P(n+1)⇒P(n+2))$ is equivalent to $P(n+1)⇒P(n+2)$, which means that assuming $P(n)⇒P(n+1)$ doesn't really help. – Fabio Somenzi 39 mins ago

$\endgroup$
  • $\begingroup$ The equivalence you claim does not hold. $\endgroup$ – Rob Arthan Jul 9 '17 at 0:16
  • $\begingroup$ In $(A \to B) \to (B \to C)$, if $A$ is false it reduces $(\bot \to B) \to (B \to C)$ to $\top \to (B \to C)$ to $B \to C$. If A is true, it reduces to $B \to (B \to C)$ which is just $B \to C$. $\endgroup$ – DanielV Jul 11 '17 at 19:01
1
$\begingroup$

Yes, there are non-artificial examples.

Consider, for instance, the statement that, for every $n\in\mathbb N$,$$1^3+2^3+\cdots+n^3=(1+2+\cdots+n)^2.$$Let $n\in\mathbb N$ and suppose that the previous statement holds for that $n$. Then you want to prove that$$1^3+2^3+\cdots+(n+1)^3=\bigl(1+2+\cdots+(n+1)\bigr)^2.$$But$$1^3+2^3+\cdots+(n+1)^3=(1+2+\cdots+n)^2+(n+1)^3$$and$$\bigl(1+2+\cdots+(n+1)\bigr)^2=(1+2+\cdots+n)^2+2(1+2+\cdots+n)(n+1)+(n+1)^2.$$Now, in order to prove the equality between the right-hand sides of the latest two equalities, it is convenient to use the fact that$$1+2+\cdots+n=\frac{n(n+1)}2\text,$$and it is rather natural to prove it by induction.

$\endgroup$
  • 1
    $\begingroup$ Although I would have answered similarly, I think this isn't what's being asked in the body of the question. OP specifically asks for a proof of the form : $P(0)$, $P(0)\implies P(1)$; $(P(n)\implies P(n+1) )\implies (P(n+1)\implies P(n+2))$, which is different from the example you gave, I think. Here what you have is $P(n)\land Q(n) \implies P(n+1)$, and you prove $Q(n)$ by induction, which is not the same (unless I'm missing something obvious) $\endgroup$ – Max Jul 8 '17 at 17:31
  • $\begingroup$ @Max: Exactly, this answer by José Carlos Santos is not what I'm looking for. Just wanted to comment on this, but then I saw your answer :-) $\endgroup$ – user7280899 Jul 8 '17 at 17:32
  • $\begingroup$ @user419308 I see. Sorry for wasting your time. $\endgroup$ – José Carlos Santos Jul 8 '17 at 17:35
  • $\begingroup$ No, it wasn't a waste of time. Please leave your question here. $\endgroup$ – user7280899 Jul 8 '17 at 17:40
  • $\begingroup$ I don't think it was unnecessary to post your answer. Others also may think that I mean the question the way you interpreted it. So we can leave it here so that we can tell others that something like this is not what I mean. $\endgroup$ – user7280899 Jul 8 '17 at 17:41
0
$\begingroup$

This would be common in proving certain propositions involving more than one variable. For example, let us prove that for any doubly indexed sequence $a_{m,n}$ satisfying $a_{m, 0} = 1$ for all $m \in \mathbb{N}$, $a_{0, n} = 1$ for all $n \in \mathbb{N}$, and $a_{m+1, n+1} = a_{m+1, n} + a_{m, n+1} + 1$ for all $m, n \in \mathbb{N}$, then $a_{m, n} = 2 \binom{m+n}{n} - 1$ for all $m, n \in \mathbb{N}$.

We prove by induction on $m$ that for all $m \in \mathbb{N}$, we have for all $n \in \mathbb{N}$, $a_{m, n} = 2 \binom{m+n}{n} - 1$. For the base case $m = 0$, this reduces to showing for all $n \in \mathbb{N}$, $a_{0, n} = 2 \binom{n}{n} - 1$, which is easy.

For the inductive case, the inductive hypothesis would be: (1) for all $n \in \mathbb{N}$, $a_{m, n} = 2 \binom{m+n}{n} - 1$. What we need to prove is: for all $n \in \mathbb{N}$, $a_{m + 1, n} = 2 \binom{(m+1)+n}{n} - 1$. We prove this by induction on $n$. Here, the base case $n = 0$ would be $a_{m+1, 0} = 2 \binom{m+1}{0} - 1$ which again is easy. For the inductive case, the inductive hypothesis would be: (2) $a_{m+1, n} = 2 \binom{(m+1)+n}{n} - 1$. What we need to prove is: $a_{m+1, n+1} = 2 \binom{(m+1)+(n+1)}{n+1} - 1$. However, we are given that $a_{m+1, n+1} = a_{m+1,n} + a_{m,n+1} + 1$. We also know from (2) that $a_{m+1,n} = 2 \binom{m+1+n}{n} - 1$; and from a special case of (1), we know that $a_{m,n+1} = 2 \binom{m+n+1}{n} - 1$. Therefore, $a_{m+1, n+1} = 2 \binom{m+n+1}{n} + 2 \binom{m+n+1}{n+1} - 1 = 2 \binom{m+n+2}{n+1} - 1$ by Pascal's identity. Thus, the inner induction establishes $a_{m+1, n} = 2 \binom{m+1+n}{n} - 1$ for all $n \in \mathbb{N}$.

We have therefore proved the inductive case for the outer induction; therefore, we have shown what we wanted: forall $m \in \mathbb{N}$, forall $n \in \mathbb{N}$, $a_{m, n} = 2 \binom{m+n}{n} - 1$.

$\endgroup$
  • $\begingroup$ I think this is not what I asked for. $\endgroup$ – user7280899 Jul 8 '17 at 19:14
  • $\begingroup$ OK, I missed the revisions as I was formulating my answer - I think it does answer the original question which was more generally "a proof by induction where the proof of the inductive step is a proof by induction". And with the revised question, I think Fabio Somenzi's comment answers why it would be artificial. $\endgroup$ – Daniel Schepler Jul 8 '17 at 19:19
  • $\begingroup$ Thanks for your help! :-) $\endgroup$ – user7280899 Jul 8 '17 at 19:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.