How to prove by induction that a parabola corresponding to two edges intersects at atmost 2 points?
I have many parabolas that are intersecting each other. I am generating a list S from the upper segments of these parabolas. Since the corresponding two edges of a parabola intersect each other at most at 2 points, the list S can contain at most 2n – 1 items.
I want to prove this by induction. What I can think of is this:
Assume I have f(x) ≤ 2n – 1.
Base case is n = 1, f(1) ≤ 2 · 1 – 1, so f(1) <= 1.
Then assume n = k holds, so f(k) ≤ 2k – 1.
We can show that for n = k+1 holds f(k+1) &开发者_StackOverflow社区le; 2(k+1) – 1.
Am I supposed to continue like that, e.g. for n = k+2, n = k+3, …? If I continue like this, then does it mean I proved it by induction?
claim: f(n) <= 2n-1
base: for n=1, there are no intersections at all [a parabola cannot intersect with itself, so there is only one segment and: f(1)=1<=2-1=1
, so the claim for n=1 is true.
We will show that if the claim is true for an arbitrary k, it is also true for k+1.
f(k+1)<=f(k)+2
because there are additional 2 segments, at most, and therefore :
f(k+1)<=f(k)+2<=(*)2k-1+2=2k+1<=2(k+1)-1
(*)from the induction assumption
From the induction, the claim is true for each k>=1.
If i understood correctly what you are trying to prove, this proof should cover it.
精彩评论