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$
11
  • $\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$
    – user401895
    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$ 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
3
$\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$
4
  • $\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$ 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$ Jul 11 '17 at 22:04
2
$\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$
5
  • 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$ 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$
    – user401895
    Jul 8 '17 at 17:32
  • $\begingroup$ @user419308 I see. Sorry for wasting your time. $\endgroup$ Jul 8 '17 at 17:35
  • $\begingroup$ No, it wasn't a waste of time. Please leave your question here. $\endgroup$
    – user401895
    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$
    – user401895
    Jul 8 '17 at 17:41
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$
2
  • $\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
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$
3
  • $\begingroup$ I think this is not what I asked for. $\endgroup$
    – user401895
    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$ Jul 8 '17 at 19:19
  • $\begingroup$ Thanks for your help! :-) $\endgroup$
    – user401895
    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