Как по индукции доказать, что парабола, соответствующая двум ребрам, пересекает не более двух точек?

Question

У меня есть много парабол, которые пересекаются друг с другом. Я создаю список S из верхних сегментов этих парабол. Поскольку соответствующие два ребра параболы пересекаются друг с другом не более чем в 2 точках, список S может содержать не более 2n & ndash; 1 предметов.

Я хочу доказать это по индукции. То, о чем я могу думать, это:

Предположим, у меня есть f (x) & le; 2n & ndash; 1 .

Базовый случай: n = 1, f (1) & le; 2 & middot; 1 & ndash; 1 , поэтому f (1) <= 1 </em>.

Тогда предположим, что n = k верно, поэтому f (k) & le; 2k & ndash; 1 .

Мы можем показать, что для n = k + 1 выполняется f (k + 1) & le; 2 (k + 1) - 1 .

Должен ли я продолжать так, например, для n = k + 2 , n = k + 3 , & hellip ;? Если я продолжу в том же духе, значит ли это, что я доказал это по индукции?

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.

Если я правильно понял, что вы пытаетесь доказать, это доказательство должно охватывать его.