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

[Gts]

Можно ли с помощью математической индукции доказать правильность формулы любого ряда?
Например, ряд $a = 1, 2, 4, 8...n; a_n = 2^n$
Первый шаг ясен: $a_1$ справедливо, так как $2^0 = 1$
Со вторым проблема. На примере сумм арифметической прогрессии всё понятно, а вот с рядами я не понимаю куда поставить $2^{n+1}$.

Далее, например, есть сумма $1 + 2 + 3 + 100 + 200 + 300 + ... + n$ и для неё описана ошибочная формула $ S = \frac {\ n (n + 1)} {\ 2} $
Применим математическую индукцию для проверки формулы.
Проверяем $S_1 = 1$, что верно, исходя из вышезаписанной суммы.
Проверяем $S_{n+1} = 1 + 2 + 3 + 100 + 200 + 300 + ... + n + (n + 1) = \frac {\ (n + 2) (n + 1)} {\ 2} $. Тут ошибка при применении мат. индукции состоит в том, что я исходил из того, что $S_n = \frac {\ n (n + 1)} {\ 2}$ верно. А ведь эта формула справедлива только для первых трёх $n$. То есть нужно доказать, что для любого члена суммы верна эта формула. А это нужно перебрать все элементы и тогда математическая индукция не нужна. Помогите, пожалуйста, понять где ошибка в рассуждениях.

[TOTAL]

Gts в сообщении #732457 писал(а):

То есть нужно доказать, что для любого члена суммы верна эта формула. А это нужно перебрать все элементы и тогда математическая индукция не нужна. Помогите, пожалуйста, понять где ошибка в рассуждениях.

Все элементы перебирать не нужно, чтобы доказать ошибочность формулы.

[Gts]

Цитата:

Все элементы перебирать не нужно, чтобы доказать ошибочность формулы.

Ок, не все, а какую-то часть, которая может быть достаточной большой.

[mustitz]

Gts в сообщении #732457 писал(а):

Можно ли с помощью математической индукции доказать правильность формулы любого ряда?
Например, ряд $a = 1, 2, 4, 8...n; a_n = 2^n$

Формула $n$-го члена ряда это просто данность. Ее доказывать не надо. Формула суммы уже да, ее надо доказать. В твоем случае сумма будет

$$ 1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1 $$

[TOTAL]

Gts в сообщении #732465 писал(а):

Цитата:

Все элементы перебирать не нужно, чтобы доказать ошибочность формулы.

Ок, не все, а какую-то часть, которая может быть достаточной большой.

Докажите ошибочность только одной.

[mustitz]

Gts в сообщении #732457 писал(а):

Проверяем $S_{n+1} = 1 + 2 + 3 + 100 + 200 + 300 + ... + n + (n + 1) = \frac {\ (n + 2) (n + 1)} {\ 2} $. Тут ошибка при применении мат. индукции состоит в том, что я исходил из того, что $S_n = \frac {\ n (n + 1)} {\ 2}$ верно.

Мы проверили утверждение при $n=1$ и $n=2$. Следовательно, когда мы доказываем это утверждение, у нас $n>2$. В этом случае формула общего члена последовательности

$$ a_n = \left\{ \begin{array}{rl} 100, & \hbox{если $n=3$} \\ 200, & \hbox{если $n=4$} \\ 300, & \hbox {если $n=5$} \\ n, & \hbox{если $n>5$} \\ \end{array} \right. $$

И теперь мы ведем дальше. Предполагаем, что $S_n = \frac {n (n + 1)}{2}$ верно

И теперь

$$ S_{n+1} = S_n + a_{n+1} = \frac {n (n + 1)}{2} + \left\{ \begin{array}{rl} 100, & \hbox{если $n=2$} \\ 200, & \hbox{если $n=3$} \\ 300, & \hbox {если $n=4$} \\ n+1, & \hbox{если $n>4$} \\ n+1, & \hbox{если $n>5$} \\ \end{array} \right. $$

Доказать, что

$$ \frac {n (n + 1)}{2} + \left\{ \begin{array}{rl} 100, & \hbox{если $n=2$} \\ 200, & \hbox{если $n=3$} \\ 300, & \hbox {если $n=4$} \\ n+1, & \hbox{если $n>4$} \\ \end{array} \right. = \frac{(n+1)(n+2)}{2} $$

уже не получается...


А если мы пойдем дальше и предположим, что $n>10$, чтобы избавиться от рассмотрения специальных случаев, то нам надо будет проверить формулу ручками при $n=1, 2, \dots, 10$, и мы получим ошибку при $n=4$: $1+2+3+100 \ne 10$. А уже один случай нам скажет о том, что формула не справедлива.

[Gts]

mustitz в сообщении #732468 писал(а):

Gts в сообщении #732457 писал(а):

Можно ли с помощью математической индукции доказать правильность формулы любого ряда?
Например, ряд $a = 1, 2, 4, 8...n; a_n = 2^n$

Формула $n$-го члена ряда это просто данность. Ее доказывать не надо. Формула суммы уже да, ее надо доказать. В твоем случае сумма будет

$$ 1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1 $$

Видимо, я плохо понимаю суть математической индукции.
Математическая индукция

Цитата:

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: $P_1, P_2, P_3,\dots,P_n, P_{n+1},...$
Допустим, что:
1. Установлено, что $P_1$ верно. (Это утверждение называется базой индукции.)
2. Для любого $n$ доказано, что если верно $P_n$ , то верно $P_{n+1}$ . (Это утверждение называется индукционным переходом.)
Тогда все утверждения нашей последовательности верны.

Почему утверждение "бесконечной последовательности утверждений" не попадает под ряд $a = 1, 2, 4, 8...n$? Почему математическую индукцию нельзя применить для проверки формулы для вычисления члена ряда?

Кроме того, может у меня неверное понимание слов

Цитата:

Для любого $n$ доказано, что если верно $P_n$

. Эти $P_n$ я должен сам доказывать или пользоваться тем, что есть? Я так полагаю, что нужно пользоваться тем что есть, исходя из того, что пишет mustitz.


Далее, я хочу проверить формулу суммы этого ряда $S_n = 2^n - 1$. Проверяем базу индукции $S_1 = 2^1-1 = 1$, что соответствует действительности. Теперь делаем индукционный переход: к обеим частям равенства прибавляем $2^n$. Получаем $S_{n+1} = 1+2+3+...+2^{n-1}+2^n = 2^n - 1 + 2^n = 2^{n+1} - 1$, что соответствует подстановке $n+1$ в формулу $S_n = 2^n - 1$. Я верно сделал индукционный переход и прибавил именно $2^n$, а не $2^{n+1}$? Собственно, если прибавить $2^{n+1}$, то мы не получим формулу суммы при $n+1$, но у меня есть ещё сомнения по неопытности.




mustitz, спасибо за пример. У Вас там, вроде как, некоторые $n$ нужно увеличить на $1$. Суть рассуждений я понял. Спасибо.

[iifat]

Таки лучше всего начать сначала. Математическая индукция — это такой метод доказательства утверждений. Если точнее — утверждений с одним натуральным (есть обобщения, но о них потом) аргументом. Где у вас утверждения?
Что это за ряд $a=1,2,4,8,\dots n$? Что означает это таинственное $\dots n$? Если это ряд степеней двойки, то $\dots 2^n,\dots$. Если $n$ — степень двойки, то это надо оговаривать. В любом случае: где утверждение? Что вы хотите доказать?
Что конкретно — конкретно — за сумма? Что идёт после 300 и где это написано?

Gts в сообщении #732881 писал(а):

mustitz, спасибо за пример

Спасибо стоит сказать прежде всего за пример, как записываются у математиков утверждения. Хотя его вывод о том, что после 300 в сумме идёт 5 никак из ваших слов не следует.

[Gts]

Дан ряд $a=1,2,4,8, \dots 2^n, \dots $, где $n$ натуральное число.
С помощью математической индукции можно проверить утверждение, что любой член этой последовательности равен $2^n$?

[mihailm]

Gts в сообщении #732983 писал(а):

Дан ряд $a=1,2,4,8, \dots 2^n, \dots $, где $n$ натуральное число.
С помощью математической индукции можно проверить утверждение, что любой член этой последовательности равен $2^n$?

Можно, а еще можно доказать, что в последовательности где все единицы: 1,1,1,1,... на $n$-ом месте единица.

[Gts]

mihailm, вот и показали бы как сделать индукционный переход, а не ёрничали.

Предположим, что для некого ряда была найдена формула для вычисления любого элемента. Я хочу её проверить. И на примере вышеуказанного ряда я хочу увидеть как это делать.

Как бы ещё объяснить... я не уверен, что сделав просто $a_{n+1} = 2^{n+1}$ будет верно. Мне кажется, что должен быть ещё какой-то шаг. Не воспринимайте будто я издеваюсь над вами.

[AGu]

Gts в сообщении #732993 писал(а):

Предположим, что для некого ряда была найдена формула для вычисления любого элемента. Я хочу её проверить. И на примере вышеуказанного ряда я хочу увидеть как это делать.

Вы просто выбрали неудачное описание для своего "ряда" -- описание, которое делает доказывемое утверждение совсем уж тривиальным. Лучше было бы описать Вашу последовательность рекуррентно: $a_1=2$ и $a_{n+1}=2a_n$ для всех $n$. Теперь методом индукции можно доказать, что $a_n=2^n$ для всех $n$. (Думаю, с этим Вы сами легко справитесь.)

[mustitz]

Gts в сообщении #732881 писал(а):

Цитата:

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: $P_1, P_2, P_3,\dots,P_n, P_{n+1},...$
Допустим, что:
1. Установлено, что $P_1$ верно. (Это утверждение называется базой индукции.)
2. Для любого $n$ доказано, что если верно $P_n$ , то верно $P_{n+1}$ . (Это утверждение называется индукционным переходом.)
Тогда все утверждения нашей последовательности верны.

Почему утверждение "бесконечной последовательности утверждений" не попадает под ряд $a = 1, 2, 4, 8...n$? Почему математическую индукцию нельзя применить для проверки формулы для вычисления члена ряда?

$a = 1, 2, 4, 8 \dots n$ а это не утверждения. Это просто числа. Последовательность. Некоторый объект. Утверждение это некоторое высказывание, которое может быть либо истинным, либо ложным. В твоем случае $P_1$ это $1$. Единица это ложное или истинное высказывание? Нет, это не высказывание вообще. Как не высказывание "три яблока", "останкинская телебашня". А вот "У Маши есть три яблока", "Останкинская телебашня ниже CN Tower в Торонто" это уже примеры высказываний. Математические высказывания это $2+2=4$. Это истинное математическое высказывание. И $2 \cdot 2 = 5$ это пример ложного высказывания.

Когда мы берем формулу, например

$$ 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} $$

то тут у нас высказывание $P_1$ это наша формула при $n=1$: $1 = 1 \cdot (1+1) / 2$. Высказывание $P_2$ это $1+2= 2 \cdot (2+1) / 2$. Все эти высказывания (равенства) могут быть или справедливыми (истинными), или ложными.

А в случае $a_n = 2^n$... Ну это способ задания некоторой последовательности. Описание некоторого объекта. Но нет никакого утверждения

-- 05.06.2013, 16:25 --

Gts в сообщении #732983 писал(а):

Дан ряд $a=1,2,4,8, \dots 2^n, \dots $, где $n$ натуральное число.
С помощью математической индукции можно проверить утверждение, что любой член этой последовательности равен $2^n$?

Тут математическая индукция не нужна. У тебя есть высказывание $A$. Тебе из него надо вывести высказывание $A$. Но формула $A \Rightarrow A$ это аксиома математической логики. Вместо $A$ можно поставить любое другое высказывание. Например, "из того, что Кличко выше Тайсона, следует, что Кличко выше Тайсона". Или "из того, что все девушки красивые, следует, что все девушки красивые".

[provincialka]

(Оффтоп)

кстати, ряд чисел 1,2,4,8,16... можно продолжить и по другому: ...,22,24,28,36,... Правило такое: к числу прибавляется его последняя цифра

[Gts]

Про отличие высказываний от описания объекта и описание ряда с помощью рекуррентной формулы я понял.

Проясните, пожалуйста, ещё индукционный переход. У меня ещё нет понимания этого момента.

Цитата:

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: $P_1, P_2, P_3,\dots,P_n, P_{n+1},...$
Допустим, что:
1. Установлено, что $P_1$ верно. (Это утверждение называется базой индукции.)
2. Для любого $n$ доказано, что если верно $P_n$ , то верно $P_{n+1}$ . (Это утверждение называется индукционным переходом.)
Тогда все утверждения нашей последовательности верны.

Во всех примерах, которые я встречал(в том числе и на примере, который объяснял mustitz), делается предположение, что $P_n$ верно. После чего производятся манипуляции с $P_{n+1}$, в следствии которых мы можем увидеть истинность или ложность нашего предположения. Иными словами, мы не должны руками доказывать $P_n$ для каждого $n$.