Метод математической индукции

[int13]

Всех приветствую. Это опять я. Заваливший, в прошлый раз все задания.
Решил начать разбираться с нуля, попутно решая все задания в учебнике...
И затупил на методе математической индукции:

Чтобы доказать, что некоторое утверждение верно для любого натурального числа n начиная с n0, достаточно доказать, что:
а) Это утверждение верно для n=n0;
б) Если данное утверждение справедливо для некоторого натурального числа k>=n0, то оно верно также и для следующего натурального числа k+1.

Все. Больше в этом учебнике про него ничего не написано
В том же демидовиче, есть много примеров на этот метод.
Вот тут я нашел несколько примеров решений
http://www.pm298.ru/reshenie/ghryr.shtml
Но оно, либо слишком не подробно, либо я не понял логики этих решений.
Итак, если кто-нибудь в силах мне помочь разобраться в этой штуке, буду благодарен. В идеале, хотелось бы увидеть какой-нибудь разобранный простой пример, во всех подробностях и деталях.

[Trotil]

http://math.ru/lib/book/plm/v03.djvu
http://math.ru/lib/book/pdf/shen/induction.pdf

[int13]

Спасибо! Отличный ресурс и отличные книги.
Надеюсь это мне поможет.

[gefest_md]

int13 писал(а):

Вот тут я нашел несколько примеров решений
http://www.pm298.ru/reshenie/ghryr.shtml

В формальной логике формула $\dr P(0)\,\&\,\forall n\in\mathbb{N}(P(n)\to P(n+1))\to\forall n\in\mathbb{N}P(n)$ принимается за аксиому. На указанном вами сайте, в разделе матлогика об этом ни слова.

[int13]

Опять ничего понять не могу. Там дан пример:
Вычислить сумму первых n нечетных чисел.
S_n = 1 + 3 + 5 + ... + (2n - 1)
Исследуем:
s1=1, s2=4, s3=9...
Положим:
S_n = n^2
Докажем две теоремы:
1. При n=1, S_n = 1 - Справедливо.
2. Допустим, гипотеза верна для n=k, т.е S_k = k^2
Докажем, что она верна и для k+1, т.е:
S_{k + 1} = (k + 1)^2}
(до этого все понятно, далее)
Действительно:
S_{k + 1} = S_k + (2k + 1)
(??? - откуда взялось 2k+1 - не понимаю)
Но,

$$S_k = k^2$$

, отсюда:

$$S_{k + 1} = k^2 + (2k + 1) = (k+1)^2$$

, ч. т. д.
Ответ:

$$S_n=n^2$$

Следующий вопрос для самостоятельного решения:

$$ & S_n = 1 + 2 + 2^2 + 2^3 + ... + 2^{n - 1} \cr & S_1 = 2 - 1 \cr & S_2 = 2^2 - 1 \cr & S_3 = 2^3 - 1 \cr & S_n = 2^n - 1 \cr} $$

1. Проверим сумму при n=1. Верно.
2. Допустим, верно для n=k, тогда

$$S_k = 2^k - 1$$

.
Докажем, что наша гипотеза верна и для k+1:

$$ S_{k + 1} = 2^{k + 1} - 1 $$

Действительно... А что действительно?

Добавлено спустя 10 минут 33 секунды:

Второй день не могу понять метод, которому в учебнике отведено три страницы. Что за ерунда

[вздымщик Цыпа]

int13 в сообщении #157900 писал(а):

(??? - откуда взялось 2k+1 - не понимаю)

$S_k = 1+ 3+ 5 +... +2k-1$, $S_{k+1} = 1+ 3+ 5 +... + 2k-1 + 2(k+1) -1$. Следовательно, $S_{k+1} - S_k = 2(k+1) -1 = 2k + 1$.

Добавлено спустя 2 минуты 57 секунд:

int13 в сообщении #157900 писал(а):

Действительно... А что действительно?

$S_{k+1} = S_k + 2^k = 2^k - 1 + 2^k = 2\cdot 2^k - 1 = 2^{k+1} -1$

[int13]

Ух, блин, ясно! Я ведь так и думал сначала...
Теперь понятно, благодарю.

[int13]

И на закрепление.

$$ S_n = {1 \over 2} + {3 \over {2^2 }} + {5 \over {2^3 }} + ... + {{2n - 1} \over {2^n }} $$

Нужно вычислить сумму.

$$ S_1 = {1 \over 2} $$

$$ S_2 = {5 \over 4} $$

$$ S_3 = {{15} \over 8} $$

$$ S_4 = {{37} \over {16}} $$

Никакая явная зависимость не обнаруживается...

[Taras]

Раскладываем на две части - простую - геом.прогресию, и "вторую" - а там уже и производная поможет.

[int13]

Эээ.. А можно как-нибудь попроще? Без производных.
Проскакивала идея, что можно вычесть 1\2Sn и прибавить. Но я так никогда не делал, и велика вероятность ошибиться.

[gefest_md]

$a_n=\dfrac{2n-1}{2^n}=\dfrac{2n+1}{2^{n-1}}-\dfrac{2n+3}{2^n}=f(n)-f(n+1).$

Добавлено спустя 9 минут 50 секунд:

Можно так: ответ $S_n=3-\dfrac{2n+3}{2^n}$ и доказать с помощью индукции.

[int13]

А если препод спросит, как ты нашел: $S_n=3-\dfrac{2n+3}{2^n}$
Что я ему смогу ответить?
Сам придумал (подобрал\заметил). Такой ответ подойдет?

[Brukvalub]

int13 в сообщении #158049 писал(а):

Сам придумал (подобрал\заметил). Такой ответ подойдет?

Нет. Никогда не нужно врать! Скажите: "мне на форуме подсказали".

[int13]

Я имею ввиду, он может потребовать с меня какой-нибудь способ, которым я получил это выражение:
$S_n=3-\dfrac{2n+3}{2^n}$
Или, эту "гипотезу" можно выдвинуть без каких-то обьяснений?
Подозреваю, что нет.
Тогда мне все же интересно, как уважаемый gefest_md получил это выражение
А вообще, сейчас попытаюсь доказать...
Сегодня пол-дня потратил чтобы разобраться с индукцией...

Добавлено спустя 7 минут 59 секунд:

Итак, база n=1. Выражение верно.
Далее, возьмем k=n, тогда:
$S_k=3-\dfrac{2k+3}{2^k}$
Выражение должно выполняться и при k+1, тогда:

$$ S_{k + 1} = 3 - {{2k + 5} \over {2^{k + 1} }} $$

Также:

$$ S_{k + 1} - S_k = {{2k + 1} \over {2^{k + 1} }} $$

Теперь нужно приравнять эти выражения и доказать что они равны, я правильно понял?

Не.. Бред какой-то.. Сейчас еще раз все пересмотрю..

[Brukvalub]

int13 в сообщении #158052 писал(а):

Тогда мне все же интересно, как уважаемый gefest_md получил это выражение

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