Метка: мат.индукция

Под методом математической индукции понимают следующий способ доказательства: если требуется доказать истинность утверждения $latex P(n), \forall n \in \mathbb{N},$ то сначала проверяют данное утверждение для некоторого натурально числа $latex n_0$, обычно $latex n_0=1$, а потом допускают истинность выражения $latex P(k).$ Далее доказывают истинность утверждения $latex P(k+1).$

Упражнение:

Доказательство одноцветности всех лошадей — ошибочное доказательство, что все лошади одного цвета, придуманное венгерским математиком Пойа. Доказательство призвано продемонстрировать ошибки, возникающие при неправильном использовании метода математической индукции.

Доказываемое утверждение: все лошади одного цвета.

Доказательство:

Проведем доказательство по индукции.

База индукции:

Одна лошадь, очевидно, одного (одинакового) цвета.
Шаг индукции:
Пусть доказано, что любые $latex K$ лошадей всегда одного цвета. Рассмотрим $latex K+1$ каких-то лошадей. Уберем одну лошадь. Оставшиеся $latex K$ лошадей одного цвета по предположению индукции. Возвратим убранную лошадь и уберем какую-то другую. Оставшиеся $latex K$ лошадей снова будут одного цвета. Значит, все $latex K+1$ лошадей одного цвета.

Отсюда следует, что все лошади одного цвета. Утверждение доказано.

В чем ошибка?
Решение

Пример:

$latex 1)$ Доказать равенство: $latex 1^{2}+2^{2}+3^{2}+\cdots+n^{2}=\frac{n(n+1)(2n+1)}{6}, n\in \mathbb{N}.$

$latex \square$ $latex 1)$  $latex 1^{2}=\frac{1(1+1)(2+1)}{6}=1.$

$latex 2)$ Пусть данное утверждение верно для $latex n=k:$   $latex 1^{2}+\cdots+k^{2}=\frac{k(k+1)(2k+1)}{6}.$

$latex 3)$ Докажем истинность утверждения для $latex n=k+1.$

$latex \overbrace{1^{2}+2^{2}+\cdots+k^{2}}^{\frac{k(k+1)(2k+1)}{6}}+(k+1)^{2}=$

$latex \frac{(k+1)(k+2)(2(k+1)+1)}{6}$

$latex \frac{k(k+1)(2k+1)}{6}+(k+1)^{2}=$

$latex \frac{(k+1)(k+2)(2k+3)}{6}$

$latex \frac{k(k+1)(2k+1)+6(k+1)^{2}}{6}=$

$latex \frac{(k+1)(k+2)(2k+3)}{6}$

$latex k(2k^{2}+k+2k+1)+6(k^{2}+2k+1)=$

$latex (k+1)(2k^{2}+3k+4k+6)$

 $latex 2k^{3}+3k^{2}+k+6k^{2}+12k+6=$

$latex 2k^{3}+7k^{2}+6k+2k^{2}+7k+6$

$latex 2k^{3}+9k^{2}+13k+6=$

$latex 2k^{3}+9k^{2}+13k+6.$   $latex \blacksquare$

$latex 2)$ Доказать, что для всех натуральных чисел $latex n$ справедливо неравенство $latex n \leq 2^{n}$.

$latex \square$ Для $latex n=1$ неравенство принимает вид $latex 1 \leq 2$, т.е. оно справедливо.

Предположим, требуемое неравенство имеет место при некотором $latex n=k$ и покажем, что оно же справедливо и для $latex n=k+1$.

Сложим предположение индукции $latex k \leq 2^{k}$ с неравенством $latex 1 \leq 2 \leq 2^{k}$. Находим $latex k+1 \leq 2^{k}+2^{k}=2^{k+1}$, что и требовалось доказать. $latex \blacksquare$

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

Лимит времени: 0

Навигация (только номера заданий)

0 из 3 заданий окончено

Вопросы:

1. 1
2. 2
3. 3

Информация

Тестовые вопросы по вышеизложенному материалу.

Вы уже проходили тест ранее. Вы не можете запустить его снова.

Тест загружается...

Вы должны войти или зарегистрироваться для того, чтобы начать тест.

Вы должны закончить следующие тесты, чтобы начать этот:

Результаты

Правильных ответов: 0 из 3

Ваше время:

Время вышло

Вы набрали 0 из 0 баллов (0)

Средний результат
Ваш результат

Рубрики

1. Нет рубрики 0%

Ваш результат был записан в таблицу лидеров

Загрузка

Имя: E-Mail:

Капча:

1. 1
2. 2
3. 3

1. С ответом
2. С отметкой о просмотре

1. Задание 1 из 3

   1.

   Количество баллов: 1

   С помощью теста мат.индукции можно доказать:

   • Бином Ньютона
   • Некоторые равенства от 1-ой переменной
   • Дифференцируемость функции
   • Интегрируемость функции
   Правильно
   

   Неправильно
   
2. Задание 2 из 3

   2.

   Количество баллов: 1

   Расположите части метода в порядке выполнения:

   • условие задачи
   • проверка верности равенства для $$n=1$$
   • предположение верности равенства для $$n=k$$
   • проверка верности равенства для $$n=k+1$$
   Правильно
   

   Неправильно
   
3. Задание 3 из 3

   3.

   Количество баллов: 1

   Обязательно ли проверять верность равенства для n=1, либо вместо единицы можно взять и другое значение?

   • Да (во всех случаях)
   • Нет (во всех случаях)
   • В зависимости от выражения
   Правильно
   

   Неправильно
   

Список литературы:

• Лысенко З.М. Конспект лекций по курсу математического анализа.
• В.И.Коляда, А.А.Кореновский «Курс лекций по мат.анализу, часть 1» (Одесса «Астропринт» , 2009г.), стр.4.

Бином Ньютона — формула, представляющая выражение $latex (a+b)^{n}$ при $latex n>0$  в виде:

$latex (a+b)^{n}=a^{n}+C_{n}^{1}a^{n-1}b+C_{n}^{2}a^{n-2}b^{2}+$

$latex C_{n}^{3}a^{n-3}b^{3}+\cdots+C_{n}^{n-1}ab^{n-1}+b^{n}$,

где $latex C_{a}^{b}$ — число сочетаний из $latex a$ элементов по $latex b$ элементов.

$latex C_{n}^{k}=\frac {n!}{k!(n-k)!}$.

Докажем верность данного утверждения:

$latex \square$ Доказательство методом математической индукции.

$latex 1)$ Для $latex n= 1$ :

$latex a+b=C_{1}^{0}a^{1-0}b^{0}+C_{1}^{1}a^{1-1}b^{1}=$

$latex a*1+b*1=a+b.$

Для $latex n=1$ утверждение выполняется.

$latex 2)$ Предположим, что утверждение выполняется для $latex n=k$.

$latex (a+b)^{k}=C_{k}^{0}a^{k-0}b^{0}+C_{k}^{1}a^{k-1}b^{1}+$

$latex C_{k}^{2}a^{k-2}b^{2}+\cdots+C_{k}^{k-1}a^{1}b^{k-1}+C_{k}^{k}a^{0}b^{k}=$

$latex a^{k}+C_{k}^{1}a^{k-1}b+C_{k}^{2}a^{k-2}b^{2}+\cdots+$

$latex C_{k}^{k-1}a^{1}b^{k-1}+b^{k}=\sum\limits_{i=0}^{k}C_{k}^{i}a^{k-i}b^{i}.$

$latex 3)$ Докажем верность формулы для $latex n=k+1$.

Докажем, что $latex (a+b)^{k+1}=\sum\limits_{i=0}^{k+1}C_{k}^{i}a^{k-i+1}b^{i}$.

$latex (a+b)^{k+1}=(a+b)(a+b)^{k}=$

$latex (a+b)\sum\limits_{i=0}^{k}C_{k}^{i}a^{k-i}b^{i}=$

$latex \sum\limits_{i=0}^{k}C_{k}^{i}a^{k-i+1}b^{i}+\sum\limits_{i=0}^{k}C_{k}^{i}a^{k-i}b^{i+1}$

Вынесем слагаемое при $latex i=0$ из первой суммы:

$latex \sum\limits_{i=0}^{k}C_{k}^{i}a^{k-i+1}b^{i} = a^{k+1}+\sum\limits_{i=1}^{k}C_{k}^{i}a^{k-i+1}b^{i}$

Вынесем слагаемое при $latex i=k$ из последней суммы:

$latex \sum\limits_{i=0}^{k}C_{k}^{i}a^{k-i}b^{i+1}=$

$latex b^{k+1} + \sum\limits_{i=0}^{k-1}C_{k}^{i}a^{k-i}b^{i+1}=$

$latex b^{k+1}+\sum\limits_{i=1}^{k}C_{k-1}^{i}a^{k-i+1}b^{i}$

Прибавим данные суммы:

$latex=a^{k+1}+\sum\limits_{i=1}^{k}C_{k}^{i}a^{k-i+1}b^{i}+$

$latex b^{k+1}+\sum\limits_{i=1}^{k}C_{k-1}^{i}a^{k-i+1}b^{i}=$

$latex =a^{k+1}+b^{k+1}+$

$latex \sum\limits_{i=1}^{k}(C_{k}^{i}+C_{k}^{i-1})a^{k-i+1}b^{i}=$

$latex =\sum\limits_{i=0}^{0}C_{k+1}^{i}a^{k-i+1}b^{i}+$

$latex \sum\limits_{i=k+1}^{k+1}C_{k+1}^{i}a^{k-i+1}b^{i}+$

$latex \sum\limits_{i=1}^{k}C_{k+1}^{i}a^{k-i+1}b^{i}=$

$latex =\sum\limits_{i=0}^{k+1}C_{k+1}^{i}a^{k-i+1}b^{i}$ $latex \blacksquare$

Также с помощью бинома Ньютона строится треугольник Паскаля, в котором числа в строке обозначают коэффициенты при соответствующих степенях:

Примеры:

$latex 1)$ $latex (a+b)^{3}=a^{3}+3a^{2}b+\frac{3!}{1!*2!}ab^{2}+b{3}=$

       $latex a^{3}+3a^{2}b+3ab^{2}+b^{3}.$

$latex 2)$ $latex (a+b+c)^{4}=?$

$latex (a+b+c)^{4}=(a+(b+c))^{4}=$

$latex a^{4}+a^{3}(b+c)\frac{4!}{3!}+a^{2}(b+c)^{2}\frac{4!}{2!2}+$

$latex a(b+c)^{3}\frac{4!}{3!}+(b+c)^{4}=$

$latex a^{4}+a^{3}b\frac{4!}{3!}+a^{3}c\frac{4!}{3!}+a^{2}b^{2}\frac{4!}{2!2!}+2a^{2}bc\frac{4!}{2!}+$

$latex a^{2}c^{2}\frac{4!}{2!2!}+ab^{3}\frac{4!}{3!}+3ab^{2}c\frac{4!}{1*2*3}+$

$latex +3abc^{2}\frac{4!}{1*2*3}+ac^{3}\frac{4!}{3!}+$

$latex b^{4}+b^{3}c\frac{4!}{3!}+b^{2}c^{2}\frac{4!}{2!2!}+bc^{3}\frac{4!}{3!}+c^{4}=$

$latex =a^{4}+b^{4}+c^{4}+4(a^{3}b+a^{3}c+b^{3}c)+$

$latex 6(a^{2}b^{2}+a^{2}c^{2}+b^{2}c^{2})+4(b^{3}a+c^{3}a+ c^{3}b)+$

$latex 12(a^{2}bc+b^{2}ac+c^{2}ab).$

Список литературы:

• Лысенко З.М. Конспект лекций по курсу математического анализа.
• В.И.Коляда, А.А.Кореновский «Курс лекций по мат.анализу, часть 1» (Одесса «Астропринт» , 2009г.), стр.5.

Тест "Бином Ньютона"

Лимит времени: 0

Навигация (только номера заданий)

0 из 3 заданий окончено

Вопросы:

1. 1
2. 2
3. 3

Информация

Тестовые вопросы по вышеизложенной теме.

Вы уже проходили тест ранее. Вы не можете запустить его снова.

Тест загружается...

Вы должны войти или зарегистрироваться для того, чтобы начать тест.

Вы должны закончить следующие тесты, чтобы начать этот:

Результаты

Правильных ответов: 0 из 3

Ваше время:

Время вышло

Вы набрали 0 из 0 баллов (0)

Средний результат
Ваш результат

Рубрики

1. Нет рубрики 0%

Ваш результат был записан в таблицу лидеров

Загрузка

Имя: E-Mail:

Капча:

1. 1
2. 2
3. 3

1. С ответом
2. С отметкой о просмотре

1. Задание 1 из 3

   1.

   Количество баллов: 1

   Доказательство Бинома Ньютона проводится методом:

   • математической индукции
   • дедукции
   • от противного
   • приведение к определению
   Правильно
   

   Неправильно
   
2. Задание 2 из 3

   2.

   Количество баллов: 1

   С помощью Бинома Ньютона можно преобразовать выражения:

   • $$a!b!$$
   • $$\sum_{i=0}^{7}C_{n}^{k}a^{n-k}b^{k}$$
   • $$(a+b)^{11}$$
   • $$f(x)'$$
   Правильно
   

   Неправильно
   
3. Задание 3 из 3

   3.

   Количество баллов: 1

   Укажите формулу для сочетаний из n элементов по k

   • $$(n+k)/2$$
   • $$n*k!$$
   • $$\frac{n!}{k!(n-k)!}$$
   • $$\frac{n!}{k!(n-k+i)!}$$
   Правильно
   

   Неправильно