algorithm - 如何通过归纳证明两条边对应的抛物线最多相交2点？

Question

我有许多相互交叉的抛物线。我正在从这些抛物线的上段生成一个列表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，...？如果我继续这样下去，那是否意味着我通过归纳证明了它？

Answer 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，该声明都是正确的。

如果我正确理解了您要证明的内容，则该证明应涵盖它。