Monday, September 11, 2017

proof verification - induction and proper use of the inductive step



Suppose I have a conjecture of the form xN+ 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(x1)>g(x1) 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) yN+ 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 x1 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=x1?



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:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...