如何归纳证明两条边对应的抛物线最多相交2点？
我有许多相互相交的抛物线。我正在从这些抛物线的上段生成一个列表S。由于抛物线相应的两条边最多相交于 2 个点，因此列表 S 最多可以包含 2n – 1 个项目。
我想用归纳法来证明这一点。我能想到的是：
假设我有f(x) ≤ 2n – 1。
基本情况是 n = 1，f(1) ≤ 2 · 1 – 1，因此 f(1) <= 1。
然后假设n = k成立，因此f(k) ≤ 2k – 1。
我们可以证明，对于n = k+1，满足f(k+1) ≤ 2(k+1) – 1。
我是否应该继续这样，例如n = k+2，n = k+3，...？如果我继续这样下去，那是否意味着我已经通过归纳证明了呢？
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) ≤ 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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
声明：
f(n) <= 2n-1基数：对于 n=1，根本不存在交点 [抛物线不能与自身相交，因此只有一条线段并且：
f(1)=1<=2-1=1，因此 n=1 的说法为真。我们将证明，如果该主张对于任意 k 成立，那么对于 k+1 也成立。
f(k+1)<=f(k)+2因为最多还有另外 2 个段，因此：f(k+1)<=f(k)+2<=(*)2k-1+2=2k+1<=2(k+1)-1( *) 根据归纳假设
根据归纳，该主张对于每个 k>=1 都是正确的。
如果我正确理解你想要证明的内容，这个证明应该涵盖它。
claim:
f(n) <= 2n-1base: 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)+2because 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.