Suppose I have a conjecture of the form $\forall x \in \mathbb{N}^{+}$ $f(x) > g(x)$.
Without explicitly giving the functions $f$ and $g$ I would like to prove this conjecture using induction.
Specifically I have shown $f(1) > g(1)$. My inductive assumption is now that $f(x - 1) > g(x - 1)$ and I'm trying to show $f(x) > g(x)$.
I haven't been able to do this, but I've noticed that I can if I assume $f(y) > g(y)$ $\forall y \in \mathbb{N}^{+}$ such that $y < x$ instead of my inductive argument I can prove $f(x) > g(x)$.
My question is, is this ok or am I using circular logic? Typically when we use induction we use $x - 1$ to prove the $x$ case after an initial base case. For my problem it doesn't appear possible to prove $f(x) > g(x)$ without assuming that for all values less than $x$ the conjecture holds ($f$ and $g$ are recursive). I suspect that it is ok, but it sounds extremely circular and I haven't been able to convince myself that it isn't.
Note also that I've included proof verification as a tag because although I have not included the explicit proof, I have included a proof approach that I'm interested in validating.
Answer
So you just want to make the stronger assumption that some statement $P(y)$ holds for all $y < x$ instead of only for $y = x-1$?
This is totally fine. It is called strong induction and is equivalent to simple induction.
No comments:
Post a Comment