Suppose I have a conjecture of the form ∀x∈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) ∀y∈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