Monday, September 11, 2017

proof verification - induction and proper use of the inductive step



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...