Математическая индукция, два утверждения в базе

[_Ivana]

Преамбула: сын просил задачек подкинуть интересных, набрал в поисковике и скачал первую попавшуюся книжку. Потом сам почитал и впечатлился.

Решали только что задачки оттуда, на мат. индукцию. Одну задачу я смог решить только следующим образом: проверив $P(1)$ и $P(2)$, и доказав $P(n-1) ~ \& ~ P(n) \mapsto P(n+1)$. Сойдет ли это за решение задачи по данной теме?

ЗЫ как значок "И" в ТЕХе вставлять? "&" в теге просто не отображается.

[Toucan]

(значок 'И' в ТЕХе)

_Ivana в сообщении #795519 писал(а):

ЗЫ как значок "И" в ТЕХе вставлять? "&" в теге просто не отображается.

$P(n-1) ~ \& ~ P(n)$

$P(n-1) ~\& ~ P(n)$

[_Ivana]

UPD прочитал-таки задачу 1.4.4 и, похоже, это расширение индукции используется мной в данном случае. Осталось доказать его эквивалентность и потом понять, почему можно было не проверять $P(2)$.

Спасибо за "И" - оказывается, это было так просто.

[Otta]

_Ivana, эквивалентность чему? Правда, что из

_Ivana в сообщении #795519 писал(а):

$P(1)$ и $P(2)$, и ... $P(n-1) ~ \& ~ P(n) \mapsto P(n+1)$

следует истинность $P(n)$ при всех $n$.
Неправда, что в той же ситуации всегда верно $P(n)\to P(n+1)$.

[nikvic]

_Ivana в сообщении #795519 писал(а):

Сойдет ли это за решение задачи по данной теме?

Да. Например, для доказательства формулы, явно выражающей члены последовательности Фибоначчи.

[_Ivana]

Otta в сообщении #795547 писал(а):

эквивалентность чему?

В задачнике есть упражнение

Цитата:

Докажите, что аксиома индукции равносильна следующему утверждению: Если известно, что некоторое утверждение верно для некоторого $a$, и из предположения, что утверждение верно для всех натуральных чисел $k$, таких, что $a <= k < n$ вытекает его справедливость для $n$, то это утверждение верно для всех натуральных чисел $k > a$

Если это верно и я ничего не путаю, то $P(2)$ можно было не проверять.

[Otta]

_Ivana в сообщении #795554 писал(а):

Если это верно и я ничего не путаю, то $P(2)$ можно было не проверять.

Можно, если в предположение индукции Вы будете загонять истинность всех $P(k)$ при $1\le k \le n$, доказывая истинность $P(n+1)$. А не только двух предыдущих. Упражнение об этом.

[ewert]

_Ivana в сообщении #795539 писал(а):

Спасибо за "И" - оказывается, это было так просто.

Просто, но неправильно. А правильно так:

"И" "ИЛИ"
$\wedge\ \ \ \ \vee$

\wedge   \vee

[Otta]

PS По сабжу:

_Ivana в сообщении #795519 писал(а):

Одну задачу я смог решить только следующим образом:проверив $P(1)$ и $P(2)$, и доказав $P(n-1) ~ \& ~ P(n) \mapsto P(n+1)$.

Это, конечно, хорошее решение, потому что, тем самым, из истинности $P(1)$ и $P(2)$ следует истинность $P(3)$, из истинности $P(2)$ и $P(3)$ - истинность $P(4)$ и т.д.

-- 03.12.2013, 00:28 --

ewert,

(Оффтоп)

просветите, пожалста, когда какое "и" пишется? Я встречаю регулярно и то, и то, но никогда, видимо, не знала, как правильно.

[_Ivana]

Otta, я так и рассуждал. Но смутило то, что это не является классической аксиомой индукции, и более того, нет упражнений на доказательство эквивалентности этих формулировок. Или решающему предоставляется право сначала придумать этот метод а потом самому доказать строго истинность такого решения?
Ваше замечание в предыдущем посте мне надо обдумать на свежую голову, а не после 40 часов без сна. Сейчас навскидку мне трудно понять, почему вывод, основанный на меньшем количестве предпосылок не включает в себя вывод, основанный на бОльшем множестве предпосылок, включающих первые.

[ewert]

(Оффтоп)

Otta в сообщении #795571 писал(а):

пожалста, когда какое "и" пишется?

Не понял вопроса. Слово "И" всегда понимается всеми однозначно, и направления галочек -- тоже.

[iifat]

Помнится, среди нескольки эквивалентных формулировок математической индукции есть и такая: $\left(P(1)\wedge \forall n \left((\forall k\le n) P(k)\right)\Rightarrow P(n+1)\right)\Rightarrow\left(\forall n P(n)\right)$

-- 03.12.2013, 06:43 --

Иначе говоря, усложняя высказывание, можно свести к канонической формулировке

[Otta]

_Ivana в сообщении #795574 писал(а):

нет упражнений на доказательство эквивалентности этих формулировок.

А они не эквивалентны. В частности, из $P(1)$ не обязана следовать $P(2)$.
ewert

(Оффтоп)

Вопрос прост: в качестве конъюнкции обычно употребляется символ $\wedge$. Я, по крайней мере, его так употребляю. Но встречаю часто и употребление $\&$. Это неверное употребление, или оно просто значит что-то совсем другое? Просю ликбезу. Это не мой конёк.

[ewert]

(Otta)

Otta в сообщении #795583 писал(а):

Но встречаю часто и употребление $\&$. Это неверное употребление, или оно просто значит что-то совсем другое?

Нет, оно верное, конечно. И означает ровно то же, конечно. Но в матлогике (которую я не знаю, пардон, но немножко всё-таки помню) как-то не принято. А как тогда обозначать наоборот -- вертикальной чёрточкой, что ли?... или двумя?...

Нет, это хорошо только в алгоритмических языках (где набор символов ограничен). А в математической нотации -- как-то не вполне комильфо.

[Otta]

ewert

(Оффтоп)

Воть! А в моём детстве как раз логик такую кракозябру рисовал. А галку ногами вниз - все остальные.