2

Is it necessary to use the induction assumption in an induction proof?

Reason to ask is that I was doing a proof about Markov chains:

Prove that $(X_k, Y_{k+1})_{k \geq 1}$ is Markov chain. $X_0=x_0$ is given and in every round ($k \geq 1$) one first generates $Y_k \sim q(X_{k-1}, \cdot)$ (where $q$ is a probability distribution), then either sets $X_k=Y_k$ or rejects $Y_k$ as invalid and sets $X_k=Y_{k-1}$.

By induction:

$X_0 = x_0$ $Y_1 \sim q(X_0, \cdot)$ $P(Y_1 | X_0)$ OK.

Assume $n=k$ i.e. $P(Y_{k} | Y_0, ..., Y_{k-1})=P(Y_k | Y_{k-1})$ holds.

Prove $n=k+1$ holds:

on the $k$th round $X_k=Y_k$ or reject $Y_k$ and set $X_k=Y_{k-1}$, in either case $X_k$ is the value of the previous r.v.

on the $k+1$th one picks $Y_{k+1} \sim q(X_{k}, \cdot)$ so $Y_{k+1}$ only depends on the previous r.v.

It seems like I didn't need to use the induction assumption at all?

Or perhaps I need to use something to split $P(Y_{k+1} | Y_1, ..., X_k)$ to smaller parts that may include $P(Y_k | Y_{k-1})$, the induction step.

mavavilj
  • 7,270
  • 2
    You must use the inductive assumption somewhere in the inductive step or your proof is not inductive. – Landuros Feb 21 '18 at 14:30
  • @Landuros That's not true. – 5xum Feb 21 '18 at 14:30
  • @5xum But then you might not be able to go from $k$ to $k+1$? The way I've learnt it is that you must use it regardless whether you can do it or not. – Landuros Feb 21 '18 at 14:31
  • @mavavilj it would be useful to first write the statement you are trying to prove – 5xum Feb 21 '18 at 14:31
  • 6
    If you don't use the inductive assumption, then it isn't a proof by induction. This doesn't imply that the proof is false, though. – Daniel Robert-Nicoud Feb 21 '18 at 14:32
  • 1
    @DanielRobert-Nicoud Yes, that is a better way of putting it. – Landuros Feb 21 '18 at 14:32
  • @Landuros I can prove the statement "For all $n\in\mathbb N: n=n$ using induction without using the inductive assumption. For $n=1$, $1=1$ because of the law of identity. Now assume $n=n$. Then, from the law of identity, $n+1=n+1$, therefore the statement $n=n\implies n+1=n+1$ is true. – 5xum Feb 21 '18 at 14:33
  • 1
    @5xum I see what you mean. However, you haven't shown that $n = n \implies n+1=n+1$ because you simply haven't linked the two statements together via any inductive hypothesis. Please correct me if I'm wrong, I am a little confused too. If you did use the inductive hypothesis, you would say $LHS = n+1 = n+1 = RHS$, and in between you subbed in $n=n$. Similar question: https://math.stackexchange.com/questions/953509/induction-proof-without-explictly-using-the-induction-hypothesis – Landuros Feb 21 '18 at 14:35
  • 2
    Remember than the induction step in the induction proof amounts to proving that $P(n) \to P(n+1)$, for every $n$. If we have a proof of $P(n+1)$ we can use the tautology: $P(n+1) \to (P(n) \to P(n+1))$ and modus ponens to derive $P(n) \to P(n+1)$. Conclusion: the proof is fine. – Mauro ALLEGRANZA Feb 21 '18 at 14:40
  • If I understand it correctly, an induction proof uses induction principle, an axiom of Natural numbers in a specific definition. In order to use it, one can suppose a subset of $\mathbb{N}$, say $S_p$ based upon some property p of a natural number (For example, p: n is a even number or an odd number). Now, according to principle, if $0 \in S_p$, and $n\in S_p \Rightarrow (n+1)\in S_p$, only then $S_p \cong \mathbb{N}$. – Jaspreet Feb 21 '18 at 14:41
  • 1
    @Landuros I proved $Y$ is a true statement, therefore I proved $X\implies Y$ is a true statement no matter what $X$ is. Now sure, you could argue that this isn't a "true" proof by induction, but from a purely mathematical position, it is a proof by induction. – 5xum Feb 21 '18 at 14:49

1 Answers1

1

If you can prove it without using the inductive assumption, then that's just fine!

I don't have the background to comment on your specific proof, but here is one that I ran into:

enter image description here

OK, so here I proved that every natural number other than $0$ has a predecessor on the basis of the Peano Axioms. On line $6$ I have proven the base, and on lines $7$ through $11$ I prove the step, with the inductive hypothesis on line $7$. Note that I never end up using this inductive hypothesis. In fact, I don't use any of the Peano axioms except the inductive axiom. And even more strikingly: without induction I could not have proven this, because the statement does not follow from the Peano axioms without the inductive axiom. In other words, here is an example of a non-trivial (necessary!) use of induction, that did not use the inductive hypothesis.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • I think my specific example is entirely interpretable from what I've given. Since in either case the $Y_{k+1}$ variable depends on the previous variable only. But I don't see where I need the inductive assumption here. – mavavilj Feb 21 '18 at 14:36
  • @mavavilj I believe you ... I'm just not at all familiar with Markov chains. But like I said, it's perfectly possible to do a proof by induction without ever using the inductive hypothesis. I just added an example to my post. – Bram28 Feb 21 '18 at 14:40
  • @Bram28 I believe Peano Axioms are the only exception. Every other inductive proof requires the use of the inductive hypothesis. https://math.stackexchange.com/a/953511/432780 – Landuros Feb 21 '18 at 14:41
  • @Landuros: See Mauro's comment to the main question. I know you want to believe this, but it's just not true. What is true is that an inductive proof (i.e., one that uses the axiom of induction somewhere) that doesn't use the inductive hypothesis can generally be transformed to a non-inductive proof. But that doesn't make the inductive proof itself non-inductive. – John Hughes Feb 21 '18 at 14:44
  • @JohnHughes Thanks for clearing that up. I guess it'll take a while for me to totally accept it. – Landuros Feb 21 '18 at 14:47