algorithm - 2つのエッジに対応する放物線が最大で2点で交差することを帰納法で証明するにはどうすればよいですか？

Question

互いに交差している放物線がたくさんあります。これらの放物線の上部セグメントからリストSを生成しています。放物線の対応する2つのエッジは、最大で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

base：n = 1の場合、交差はまったくありません[放物線はそれ自体と交差できないため、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に当てはまります。

あなたが証明しようとしていることを私が正しく理解していれば、この証明はそれをカバーするはずです。