По индукции доказательство: Недопустимое название — Викиучебник

Содержание

Урок 27. математическая индукция — Алгебра и начала математического анализа — 11 класс

Алгебра и начала математического анализа, 11 класс

Урок №27. Математическая индукция.

Глоссарий

Индукция; принцип математической индукции; полная индукция; неполная индукция.

Основная литература:

Колягин Ю.М., Ткачева М.В, Федорова Н.Е. и др., под ред. Жижченко А.Б. Алгебра и начала математического анализа (базовый и профильный уровни) 11 кл. – М.: Просвещение, 2014.

Дополнительная литература:

Орлова Е. А., Севрюков П. Ф., Сидельников В. И., Смоляков А.Н. Тренировочные тестовые задания по алгебре и началам анализа для учащихся 10-х и 11-х классов: учебное пособие – М.: Илекса; Ставрополь: Сервисшкола, 2011.

Теоретический материал для самостоятельного изучения

Если рассмотреть значения квадратного трехчлена при равного они соответственно равны . Заметим, что эти числа являются простыми. Исходя из этого, можно сделать вывод, что при любом натуральном n число является простым. Но так ли это на самом деле?

Мы проверили справедливость утверждения при n от 1 до 14. Возьмем n равное 41 и подставим в наш квадратный трехчлен.

При n = 41, получаем

-составное число!

Получили составное число, т.е. противоречие нашему утверждению.

Для строгого доказательства утверждений на множестве натуральных чисел используют метод полной математической индукции. Продемонстрируем этот метод на примере:

Первым шагом проверим базу индукции, т.е. справедливость неравенства при наименьшем натуральном числе n=1

1 шаг: при n=1

неравенство выполняется

Вторым шагом будет индуктивное предположение, т.е. предположим, что неравенство верно для некоторого натурального n.

2 шаг: предположим, что неравенство верно при некотором натуральном n.

неравенство выполняется.

Далее выполним индуктивный переход, т. е. докажем, что из предположения, сделанного на втором шаге следует справедливость аналогичного неравенства для следующего натурального числа n+1

следует

умножим обе части на положительное число 2

Получим верное неравенство

Но!

Т.к.

Из следует

Т.о. доказательство методом полной математической индукции состоит в:

1) Проверке справедливости утверждения при ;

2) Доказательстве, что если утверждение верно для натурального числа , то оно верно и для следующего за ним .

Пример:

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

  1. При n=1 неравенство верно
  1. Предположим, что для некоторого натурального n неравенство верно.

Докажем, что если неравенство верно для некоторого n, то оно верно и для , т.е.

Прибавим к обеим частям верного по предположению равенства число :

Преобразуем правую часть равенства:

Таким образом из справедливости равенства

Следует справедливость равенства

Пример:

Докажите, что делится на 133 без остатка.

1 шаг: при

– произведение делится на 133 без остатка.

2 шаг: предположим, что сумма делится на 133 без остатка.

3 шаг:докажем, что делится на 133 без остатка.

В ходе преобразований получаем сумму, которая делится на 133 без остатка, т.к. первое ее слагаемое содержит множитель который делится на 133 без остатка по предположению индукции сделанного на 2 шаге, а во втором слагаемом одним из множителей является 133. Следовательно, и вся сумма делится на 133 без остатка.

Math.ru


Лидия Ивановна Головина, Иссак Моисеевич Яглом

Физматгиз, 1961. 100 с.

Тираж 35000 экз.

Серия Популярные лекции по математике, выпуск 21



Загрузить (Mb)
djvu (1.25) pdf (-) ps (-) html (-) tex (-)

Настоящая книжка, рассчитанная в первую очередь на
учащихся старших (9-го и 10-го) классов средней школы, учителей
математики и студентов физико-математических факультетов пединститутов,
примыкает к книжке И. С. Соминского «Метод математической индукции»,
составляющей 3-й выпуск серии «Популярные лекции по математике», и
может рассматриваться как ее продолжение; тем читателям, которые
знакомы с книжкой И. С. Соминского, она будет особенно интересна.

Книжка содержит 37 примеров, решения которых
подробно разобраны, и 40 задач, сопровождаемых краткими указаниями.
Она посвящена разнообразным применениям метода математической индукции
к решению геометрических задач. Наиболее поучительны здесь, по нашему
мнению, различные аспекты метода математической индукции; отдельные
(но, разумеется, не все) примеры и задачи могут также представлять и
определенный самостоятельный интерес.

В основу книжки положены две лекции, прочитанные
И. М. Ягломом московским школьникам — участникам школьного
математического кружка при Московском государственном университете.

Л. И. Головина
И. М. Яглом


Содержание

Предисловие

Введение: Что такое метод математической индукции?
(примеры 1–4, задачи 1–2)

§ 1. Вычисление по индукции (примеры 5–9, задачи 3–5)

§ 2. Доказательство по индукции (примеры 10–19, задачи 6–13)

§ 3. Построение по индукции (примеры 20–23, задачи 14–16)

§ 4. Нахождение геометрических мест по индукции (примеры 24–25, задачи 17–23)

§ 5. Определение по индукции (примеры 26–27, задачи 24–32)

§ 6. Индукция по числу измерений (примеры 28–37, задачи 33–40)

    1.
Вычисление с помощью индукции по числу измерений (пример 28, задача 33)

    2.
Доказательство с помощью индукции по числу измерений
(примеры 29–35, задачи 34–39)

    3.
Нахождение геометрических мест с помощью индукции по числу измерений (пример 36)

    4.
Определение с помощью индукции по числу измерений
(пример 37, задача 40)




Загрузить (Mb)
djvu (1. 25) pdf (-) ps (-) html (-) tex (-)

Подготовка школьников к ЕГЭ и ОГЭ (Справочник по математике — Алгебра

Конечные числовые суммы

      Пусть   n   – произвольное натуральное число. Тогда справедливы следующие формулы, которые называют конечными числовыми суммами:

      Сумма бесконечно убывающей геометрической прогрессии является простейшим примером бесконечной числовой суммы (числового ряда). Ряды изучают в ВУЗовских курсах математики.

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

      К изложению одного из мощнейших методов доказательства этих, а также подобных формул, – методу (принципу) математической индукции мы сейчас и переходим.

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

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

  1. непосредственно проверили, что формула верна при   n = 1 ,
  2. доказали, что из справедливости формулы для некоторого номера   n ,   вытекает её справедливость для номера   n + 1 .

      Тогда в силу метода (принципа) математической индукции можно утверждать, что формула верна для всех натуральных чисел   n .

      Для примера дадим доказательство одной из формул, приведенных в предыдущем разделе.

      Пример 1. Доказать, что при всех натуральных   n   верна формула

(1)

      Решение. Для доказательства воспользуемся методом математической индукции:

  1. В случае   n = 1   формула (1) имеет вид

    и является верной.

  2. Докажем, что из справедливости равенства (1), вытекает справедливость равенства

    полученного из равенства (1) при помощи замены   n   на   n + 1 .

          Действительно,

          Следовательно, формула (2) верна, откуда из принципа математической индукции заключаем, что формула (1) верна для всех натуральных значений   n .

      Пример 2. Доказать, что число   n5 – n   делится на   5   при всех натуральных значениях n .

      Решение. Для доказательства снова воспользуемся методом математической индукции:

  1. В случае   n = 1   число   n5 – n   равно   0   и, конечно же, делится на   5 .

    Таким образом, при   n = 1   требуемое утверждение верно.

  2. Теперь докажем, что из того, что число   n5 – n   делится на   5   вытекает, что число

    (n + 1)5 – (n + 1)

    также делится на   5 .

          Действительно, пусть

    n5n = 5k ,

    где   .

          Тогда поскольку

    (n + 1)5 = n5 + 5n4 +
    + 10n3 + 10n2 + 5n + 1

    (см. Таблицу 1 из раздела справочника «Формулы сокращенного умножения: степень суммы и степень разности»), то

    (n + 1)5 – (n + 1) =
    = (n5n)+
    + 5n4 +
    + 10n3 + 10n2 + 5n =
    = 5k + 5n4 + 10n3 +
    + 10n2 + 5n =
    = 5 (k + n4 +
    + 2n3 + 2n2 + n) ,

    т. е. делится на   5 .

          В соответствии с принципом математической индукции все доказано.

 

      На сайте можно также ознакомиться с нашими учебными материалами для подготовки к ЕГЭ и ОГЭ по математике.

Страница не найдена — ПриМат

© 2012-2016: Нохум-Даниэль Блиндер (11), Анастасия Лозинская (10), Елизавета Савицкая (8), Игорь Любинский (8), Юлия Стерлянко (8), Денис Стехун (8), Олег Шпинарев (7), Александр Базан (7), Валентин Малявко (7), Анна Чалапчий (7), Константин Берков (7), Кирилл Волков (6), Татьяна Корнилова (6), Влад Радзивил (6), Максим Швандт (6), Людмила Рыбальченко (6), Даниил Радковский (5), Влад Недомовный (5), Александр Онищенко (5), Андрей Метасов (5), Денис Базанов (5), Александр Ковальский (5), Александр Земсков (5), Марина Чайковская (5), Екатерина Шибаева (5), Мария Корень (5), Анна Семененко (5), Мария Илларионова (5), Сергей Черкес (5), Алиса Ворохта (5), Валерия Заверюха (5), Елизавета Снежинская (5), Вадим Покровский (5), Алина Малыхина (4), Андрей Лисовой (4), Полина Сорокина (4), Кирилл Демиденко (4), Дмитрий Стеценко (4), Александр Рапчинский (4), Святослав Волков (4), Иван Мясоедов (4), Владислав Стасюк (4), Алёна Гирняк (4), Николай Царев (4), Валентин Цушко (4), Павел Жуков (4), Роман Бронфен-Бова (4), Артём Романча (4), Анна Шохина (4), Иван Киреев (4), Никита Савко (4), Кондрат Воронов (4), Алина Зозуля (4), Иван Чеповский (4), Артем Рогулин (4), Игорь Чернега (4), Даниил Кубаренко (4), Ольга Денисова (4), Татьяна Осипенко (4), Яков Юсипенко (4), Ольга Слободянюк (4), Руслан Авсенин (4), Екатерина Фесенко (4), Дмитрий Заславский (4), Константин Грешилов (3), Марина Кривошеева (3), Денис Куленюк (3), Константин Мысов (3), Мария Карьева (3), Константин Григорян (3), Колаев Демьян (3), Станислав Бондаренко (3), Ильдар Сабиров (3), Владимир Дроздин (3), Кирилл Сплошнов (3), Карина Миловская (3), Дмитрий Козачков (3), Мария Жаркая (3), Алёна Янишевская (3), Александра Рябова (3), Дмитрий Байков (3), Павел Загинайло (3), Томас Пасенченко (3), Виктория Крачилова (3), Таисия Ткачева (3), Владислав Бебик (3), Илья Бровко (3), Максим Носов (3), Филип Марченко (3), Катя Романцова (3), Илья Черноморец (3), Евгений Фищук (3), Анна Цивинская (3), Михаил Бутник (3), Станислав Чмиленко (3), Катя Писова (3), Дмитрий Дудник (3), Дарья Кваша (3), Игорь Стеблинский (3), Артем Чернобровкин (3), Виктор Булгаков (3), Дмитрий Мороз (3), Богдан Павлов (3), Игорь Вустянюк (3), Андрей Яроцкий (3), Лаура Казарян (3), Екатерина Мальчик (3), Анатолий Осецимский (3), Иван Дуков (3), Дмитрий Робакидзе (3), Вячеслав Зелинский (3), Данила Савчак (3), Дмитрий Воротов (3), Стефания Амамджян (3), Валерия Сиренко (3), Георгий Мартынюк (3), Виктор Иванов (3), Вячеслав Иванов (3), Валерия Ларикова (3), Евгений Радчин (3), Андрей Бойко (3), Милан Карагяур (3), Александр Димитриев (3), Иван Василевский (3), Руслан Масальский (3), Даниил Кулык (3), Стас Коциевский (3), Елизавета Севастьянова (3), Павел Бакалин (3), Антон Локтев (3), Андрей-Святозар Чернецкий (3), Николь Метри (3), Евелина Алексютенко (3), Даниил Крутоголов (2), Наталия Писаревская (2), Дэвид Ли (2), Александр Коломеец (2), Александра Филистович (2), Евгений Рудницкий (2), Олег Сторожев (2), Евгения Максимова (2), Алексей Пожиленков (2), Юрий Молоканов (2), Даниил Кадочников (2), Александр Колаев (2), Александр Гутовский (2), Павел Мацалышенко (2), Таня Спичак (2), Радомир Сиденко (2), Владислав Шиманский (2), Илья Балицкий (2), Алина Гончарова (2), Владислав Шеванов (2), Андрей Сидоренко (2), Александр Мога (2), Юлия Стоева (2), Александр Розин (2), Надежда Кибакова (2), Майк Евгеньев (2), Евгений Колодин (2), Денис Карташов (2), Александр Довгань (2), Нина Хоробрых (2), Роман Гайдей (2), Антон Джашимов (2), Никита Репнин (2), Инна Литвиненко (2), Яна Юрковская (2), Гасан Мурадов (2), Богдан Подгорный (2), Алексей Никифоров (2), Настя Филипчук (2), Гук Алина (2), Михаил Абабин (2), Дмитрий Калинин (2), Бриткариу Ирина (2), Никита Шпилевский (2), Алексей Белоченко (2), Юлиана Боурош (2), Никита Семерня (2), Владимир Захаренко (2), Дмитрий Лозинский (2), Яна Колчинская (2), Юрий Олейник (2), Кирилл Бондаренко (2), Елена Шихова (2), Татьяна Таран (2), Наталья Федина (2), Настя Кондратюк (2), Никита Гербали (2), Сергей Запорожченко (2), Николай Козиний (2), Георгий Луценко (2), Владислав Гринькив (2), Александр Дяченко (2), Анна Неделева (2), Никита Строгуш (2), Настя Панько (2), Кирилл Веремьев (2), Даниил Мозгунов (2),

МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ • Большая российская энциклопедия

МАТЕМАТИ́ЧЕСКАЯ ИНДУ́КЦИЯ, ме­тод до­ка­за­тель­ст­ва ма­те­ма­тич. 2$, то из спра­вед­ли­во­сти (1) при $n=N$ вы­те­ка­ет спра­вед­ли­вость (1) при $n=N+ 1$ (ка­ко­во бы ни бы­ло $N$), т. е. (1) спра­вед­ли­во при всех на­ту­раль­ных $n$.

До­ка­за­тель­ст­во ут­вер­жде­ния $A(1)$ со­став­ля­ет пер­вый шаг (ба­зис) ин­дук­ции, а до­ка­за­тель­ст­во ут­вер­жде­ния $A(n+1)$ в пред­по­ло­же­нии, что вер­но $A(n)$, на­зы­ва­ет­ся ша­гом ин­дук­ции или ин­дук­ци­он­ным пе­ре­хо­дом. При этом $n$ на­зы­ва­ет­ся па­ра­мет­ром ин­дук­ции, а пред­по­ло­же­ние $A(n)$ при до­ка­за­тель­ст­ве ут­вер­жде­ния $A(n+1)$ на­зы­ва­ет­ся ин­дук­тив­ным пред­по­ло­же­ни­ем.

Прин­цип М. и. яв­ля­ет­ся так­же ос­но­ва­ни­ем для ин­дук­тив­ных оп­ре­де­ле­ний. Про­стей­шим при­ме­ром та­ко­го оп­ре­де­ле­ния яв­ля­ет­ся оп­ре­де­ле­ние свой­ст­ва «быть сло­вом дли­ны $n$ в дан­ном ал­фа­ви­те $𝒜=\{ a_1,a_2,…,a_k \}$». Ба­зис ин­дук­ции: ка­ж­дая бу­к­ва ал­фа­ви­та $𝒜$ есть сло­во дли­ны 1. Ин­дук­ци­он­ный пе­ре­ход: ес­ли $E$ – сло­во дли­ны $n$ в $𝒜$, то ка­ж­дое сло­во $Ea_i$, где к сло­ву $E$ спра­ва при­пи­сы­вает­ся бук­ва $a_i$, где $1 ⩽ i ⩽ k$, есть так­же сло­во дли­ны $n+ 1$ в $𝒜$. Ин­дук­ция мо­жет на­чи­нать­ся с $n=0$, т. е. с пус­то­го сло­ва.

М. и. мо­жет при­ме­нять­ся для до­ка­за­тель­ст­ва ут­вер­жде­ний $A(x)$, в ко­то­рых па­ра­метр $x$ про­бе­га­ет то или иное мно­же­ст­во, впол­не упо­ря­до­чен­ное по не­ко­то­ро­му транс­фи­нит­но­му ти­пу; в этом слу­чае го­во­рят о транс­фи­нит­ной ин­дук­ции.

доказательство по индукции — это… Что такое доказательство по индукции?

доказательство по индукции
мат. inductive proof, proof by induction

Большой англо-русский и русско-английский словарь.
2001.

  • доказательство по аналогии
  • доказательство по иску

Смотреть что такое «доказательство по индукции» в других словарях:

  • ДОКАЗАТЕЛЬСТВО МЕТОДОМ ИНДУКЦИИ — (proof by induction) Метод, доказывающий существование некоего свойства у членов последовательности. Сначала проверяется в лоб наличие его у нескольких первых, затем высказывается предположение, что им обладают все – до N го включительно и… …   Экономический словарь

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

  • ДОКАЗАТЕЛЬСТВО — рассуждение, устанавливающее истинность к. л. утверждения путем приведения др. утверждений, истинность которых уже установлена. В Д. различаются тезис утверждение, которое нужно доказать, и основание, или аргументы, те утверждения, с помощью… …   Философская энциклопедия

  • Метод математической индукции — Математическая индукция в математике один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 база индукции, а затем… …   Википедия

  • Принцип математической индукции — Математическая индукция в математике один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 база индукции, а затем… …   Википедия

  • КОСМОЛОГИЧЕСКОЕ ДОКАЗАТЕЛЬСТВО БЫТИЯ БОГА — своеобразная рационализация основного догмата авраамических религий о Боге как созидателе мирового порядка (космоса), отвечающая Книге Бытия из Ветхого завета. Оно называется космологическим (но не просто логическим ) потому, что апеллирует к… …   Современный философский словарь

  • Математическая индукция — Математическая индукция  один из методов математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала пров …   Википедия

  • Теорема Бертрана о выборах — В комбинаторике, Теорема Бертрана о выборах, названая в честь Жозефа Бертрана, который опубликовал ее в 1887 году  утверждение, доказывающее ответ на вопрос «Какова вероятность того, что на выборах с участием двух кандидатов, в которых… …   Википедия

  • Неравенство Бернулли — утверждает: если , то для всех Доказательство Доказательство неравенства проводится методом математической индукции по n. При n = 0 неравенство, очевидно, верно. Допустим, что оно верно для n, докажем его вернос …   Википедия

  • Доказательства вообще — Доказательство (Demonstratio) есть выведение истинности какого либо положения (на основании силлогистических законов) из других положений. Доказывать можно лишь положения (понятия могут быть определяемы, факты объясняемы и показываемы), и притом… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Coq — (фр.  coq  петух)  интерактивное программное средство доказательства теорем, использующее собственный язык функционального программирования (Gallina) с зависимыми типами. Позволяет записывать математические теоремы и их… …   Википедия

Книги

  • Практическая логика. Учебное пособие для академического бакалавриата, Ивин А.А.. В учебном пособии описаны основы логики. Даны задачи и законы логики, описана неклассическая логика и ее направления. Рассмотрено доказательство, раскрыты его структура и виды, способы… Подробнее  Купить за 1093 грн (только Украина)
  • Практическая логика. Учебное пособие для академического бакалавриата, Ивин А.А.. В учебном пособии описаны основы логики. Даны задачи и законы логики, описана неклассическая логика и ее направления. Рассмотрено доказательство, раскрыты его структура и виды, способы… Подробнее  Купить за 845 руб
  • Практическая логика 2-е изд., испр. и доп. Учебное пособие для академического бакалавриата, А. А. Ивин. В учебном пособии описаны основы логики. Даны задачи и законы логики, описана неклассическая логика и ее направления. Рассмотрено доказательство, раскрыты его структура и виды, способы… Подробнее  Купить за 499 руб электронная книга

Другие книги по запросу «доказательство по индукции» >>

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

Математическая индукция лежит в основе одного из самых распространенных методов математических доказательств. С его помощью можно доказать большую часть формул с натуральными числами n, например, формулу нахождения суммы первых членов прогрессии Sn=2a1+n-1d2·n, формулу бинома Ньютонаa+bn=Cn0·an·Cn1·an-1·b+…+Cnn-1·a·bn-1+Cnn·bn.

В первом пункте мы разберем основные понятия, потом рассмотрим основы самого метода, а затем расскажем, как с его помощью доказывать равенства и неравенства.

Понятия индукции и дедукции

Для начала рассмотрим, что такое вообще индукция и дедукция.

Определение 1

Индукция – это переход от частного к общему, а дедукция наоборот – от общего к частному.

Например, у нас есть утверждение: 254 можно разделить на два нацело. Из него мы можем сделать множество выводов, среди которых будут как истинные, так и ложные. Например, утверждение, что все целые числа, которые имеют в конце цифру 4, могут делиться на два без остатка – истинное, а то, что любое число из трех знаков делится на 2 – ложное.

В целом можно сказать, что с помощью индуктивных рассуждений можно получить множество выводов из одного известного или очевидного рассуждения. Математическая индукция позволяет нам определить, насколько справедливы эти выводы.

Допустим, у нас есть последовательность чисел вида 11·2, 12·3, 13·4, 14·5,…, 1n(n+1), где n обозначает некоторое натуральное число. В таком случае при сложении первых элементов последовательности мы получим следующее:

S1=11·2=12, S2=11·2+12·3=23, S3=11·2+12·3+13·4=34,S4=11·2+12·3+13·4+14·5=45,. ..

Используя индукцию, можно сделать вывод, что Sn=nn+1. В третьей части мы докажем эту формулу.

В чем заключается метод математической индукции

В основе этого метода лежит одноименный принцип. Он формулируется так:

Определение 2

Некое утверждение будет справедливым для натурального значения n тогда, когда 1) оно будет верно при n=1 и 2) из того, что это выражение справедливо для произвольного натурального n=k, следует, что оно будет верно и при n=k+1.

Нужна помощь преподавателя?

Опиши задание — и наши эксперты тебе помогут!

Описать задание

Применение метода математической индукции осуществляется в 3 этапа:

  1. Для начала мы проверяем верность исходного утверждения в случае произвольного натурального значения n (обычно проверка делается для единицы).
  2. После этого мы проверяем верность при n=k.
  3. И далее доказываем справедливость утверждения в случае, если n=k+1.

Как применять метод математической индукции при решении неравенств и уравнений

Возьмем пример, о котором мы говорили ранее.

Пример 1

Докажите формулу Sn=11·2+ 12·3+…+1n(n+1)=nn+1.

Решение

Как мы уже знаем, для применения метода математической индукции надо выполнить три последовательных действия.

  1. Для начала проверяем, будет ли данное равенство справедливым при n, равном единице. Получаем S1=11·2=11+1=12. Здесь все верно.
  2. Далее делаем предположение, что формула Sk=kk+1 верна.
  3. В третьем шаге нам надо доказать, что Sk+1=k+1k+1+1=k+1k+2, основываясь на справедливости предыдущего равенства.

Мы можем представить k+1 в качестве суммы первых членов исходной последовательности и k+1:

Sk+1=Sk+1k+1(k+2)

Поскольку во втором действии мы получили, что Sk=kk+1, то можно записать следующее:

Sk+1=Sk+1k+1(k+2).

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

Sk+1=Sk+1k+1(k+2)=kk+1+1k+1(k+2)==k(k+2)+1k+1(k+2)=k2+2k+1k+1(k+2)=(k+1)2k+1(k+2)=k+1k+2

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

Ответ: предположение о формуле Sn=nn+1 является верным.

Возьмем более сложную задачу с тригонометрическими функциями.

Пример 2

Приведите доказательство тождества cos2α·cos4α·…·cos2nα=sin 2n+1α2nsin 2α.

Решение

Как мы помним, первым шагом должна быть проверка верности равенства при n, равном единице. Чтобы это выяснить, нам надо вспомнить основные тригонометрические формулы.

cos 21=cos 2αsin 21+1α21sin 2α=sin 4α2sin 2α=2sin 2α·cos 2α2sin 2α=cos 2α

Следовательно, при n, равном единице, тождество будет верным.

Теперь предположим, что его справедливость сохранится при n=k, т.е. будет верно, что cos 2α·cos 4α·…·cos 2kα=sin 2k+1α2ksin 2α.

Доказываем равенство cos 2α·cos 4α·…·cos 2k+1α=sin 2k+2α2k+1sin 2α для случая, когда n=k+1, взяв за основу предыдущее предположение.

Согласно тригонометрической формуле,

sin 2k+1α·cos 2k+1α==12(sin(2k+1α+2k+1α)+sin(2k+1α-2k+1α))==12sin(2·2k+1α)+sin 0=12sin 2k+2α

Следовательно,

cos 2α·cos 4α·. ..·cos 2k+1α==cos 2α·cos 4α·…·cos 2kα·cos 2k+1α==sin 2k+1α2k sin 2α·cos 2k+1α=12·sin 2k+1α2ksin 2α=sin 2k+2α2k+1sin 2α

Ответ:  На этом тождество можно считать доказанным. Мы успешно применили для этого метод математической индукции. Точно так же мы можем доказать справедливость формулы бинома Ньютона.

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

Доказательство индукцией

Доказательство индукцией
Доказательства по индукции

Доказательство по индукции похоже на обычное доказательство, в котором каждый шаг
должно быть оправдано. Однако в нем используется хитрый прием, который позволяет вам
доказать утверждение о произвольном числе n, предварительно доказав
это верно, когда n равно 1, а затем предполагая, что это верно для n = k и показывая
это верно для n = k + 1. Идея в том, что если вы хотите показать это кому-то
может подняться на n-й этаж пожарной лестницы, вам нужно только показать, что
вы можете подняться по лестнице на пожарную лестницу (n = 1), а затем показать, что
умеешь подниматься по лестнице с любого уровня пожарной лестницы (n = k)
на следующий уровень (n = k + 1).

Если вы сделали доказательство по индукции до того, как вас, возможно, попросили
предположим случай n-1 и покажем случай n, или предположим случай n и покажем
случай n + 1. Это то же самое, что я объясняю здесь, но я
используйте другую букву, потому что я думаю, это позволяет избежать путаницы, когда
пытаясь выяснить, в чем заключается каждый случай.

Пример 1. Докажите 1 + 2 + … + n = n (n + 1) / 2, используя доказательство по индукции.

n = 1: 1 = 1 (2) / 2 = 1 проверка.

Предположим, что выполняется n = k: 1 + 2 +… + k = k (k + 1) / 2 (индукционная гипотеза)

Показать n = k + 1: 1 + 2 + … + k + (k + 1) = (k + 1) ((k + 1) +1) / 2

Я просто подставляю k и k + 1 в формулу, чтобы получить эти строки.
Обратите внимание, что я записываю то, что хочу доказать.

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

1 + 2 + … + (к + 1) = 1 + 2 + … + к + (к + 1)

= k (k + 1) / 2 + (k + 1) по гипотезе индукции

= (k (k + 1) +2 (k + 1)) / 2 на 2/2 = 1 и распределение деления по сложению

= (k + 2) (k + 1) / 2 по распределению умножения над сложением

= (k + 1) (k + 2) / 2 по коммутативности умножения

QED


Пример 2:
Докажите, что если P1 P2…Pn — коллинеарные точки в пространстве, удовлетворяющие аксиомам
инцидентности и промежуточности, так что каждый Pj находится между P (j-1) и
P (j + 1) для j = 2 … (n-1), тогда Pj находится между P1 и Pn для любого j = 2 … (n-1).


Это другой вид доказательства по индукции, потому что в нем нет смысла.
пока n = 3. Итак, мы начинаем с n = 3, а затем показываем, что если n = k, мы получаем n = (k + 1), таким образом
доказывая утверждение для n = 3,4,5,6, …

n = 3: P2 находится между P1 и P3, подразумевает, что P2 находится между P1 и P3.Сделанный

Предположим, что n = k: , если P1 P2 … Pk коллинеарные точки
такой, что каждый Pj находится между P (j-1) и
P (j + 1) для j = 2 … (k-1), тогда Pj находится между P1 и Pk для любого j = 2 … (k-1).
Гипотеза индукции.

Показать n = k + 1: , если P1 P2 … P (k + 1) коллинеарные точки
такой, что каждый Pj находится между P (j-1) и
P (j + 1) для j = 2 … k, тогда Pj находится между P1 и P (k + 1) для любого j = 2 … (k).

K точек P1, P2, … P (k-1) P (k + 1) удовлетворяют условиям индукции
гипотеза, чтобы мы знали
Pj находится между P1 и P (k + 1) для любого j = 2… (к-1).

K точек P1, P3, P4 … Pk P (k + 1) также
удовлетворяют условиям индукции
гипотеза, поэтому мы знаем, что Pj находится между P1 и P (k + 1) для любого j = 3 … (k).

QED

Пример 3: Докажите, что любое пространство, удовлетворяющее аксиомам инцидентности и
Промежуток, содержащий точку, имеет бесконечное количество различных
коллинеарные точки.

Если я могу показать, что пространство содержит n точек для любого числа n, тогда
он должен иметь бесконечное количество точек.Так
Я проведу доказательство индукцией по количеству точек n.

n = 1: Содержит ли пробел хотя бы одну точку? Да, это делает
гипотеза («которая содержит точку»)

Предположим, мы нашли n = k коллинеарных точек (гипотеза индукции)


Покажите, что мы можем найти n = k + 1 коллинеарных точек.
Нам нужно найти еще одну точку.

А теперь нарисуем картинку. Если мы поставим все точки на линию
тогда легко добавить еще одну точку в конце.Сделать это проще
если баллы в порядке. Другими словами было бы проще
доказать:
любое пространство, удовлетворяющее Аксиомам инцидентности и
Промежуток, содержащий точку, имеет бесконечное количество различных
коллинеарные точки P1, P2, … такие, что каждая Pi находится между P (i + 1) и
P (i-1) для i> 1. Итак, мы изменим нашу гипотезу индукции.

Предположим, что n = k: , что у нас есть n = k коллинеарных точек P1, P2, … Pk таких, что
P2 находится между P1 и P3, P3 находится между P4 и P2… P (k-1) находится между P (k-2)
и Pk. (Новая гипотеза индукции)

Показать n = k + 1:
что у нас есть n = k + 1 коллинеарных точек P1, P2, … P (k + 1) таких, что
P2 находится между P1 и P3, P3 находится между P4 и P2, … P (k) находится между P (k-1)
и P (k + 1).

По предположению индукции мы имеем k коллинеарных точек. Находим k + 1
точку, используя аксиому B2, которая гласит, что при B = P (1) и D = Pk мы можем найти
новая точка E = P (k + 1) такая, что Pk находится между P (1) и P (k + 1). *

Теперь нам нужно показать, что P (k + 1) отличается от Pj для любого j = 1,2…к.

По примеру 2. мы знаем, что Pj находится между P1 и Pk для j = 2,3 … k-1. *

Однако P (k) находится между P1 и P (k + 1), поэтому по аксиоме B3 P (k + 1) не может быть
Pj для j = 2,3 … k-1.

Поскольку P (k + 1) уже отличался от P1 и Pk, мы закончили.

QED?


В этом доказательстве есть две ошибки! Когда мы цитировали Пример 2,
мы могли сделать это, только если k было больше или равно 3! Также
на самом первом шаге мы предполагаем, что k было больше или равно 2!
См. * В доказательстве.

Затем мы должны выполнить эти случаи в начале в дополнение к n = 1.

n = 2: Согласно аксиоме I3 существуют три точки, которые не являются коллинеарными.
Пусть P1 и P2 — две из этих точек. Эти пункты «по порядку»
потому что их всего двое.

n = 3: В случае n = 2 мы знаем, что у нас есть две коллинеарные точки P1 и P2.
По аксиоме B3 мы можем найти P3 такое, что P2 находится между P1 и P3.
Они уже в порядке только Axiom B3.(n-1) используя определение
производная.

3) Докажите, что пространство с n точками
чьи прямые — это любая пара различных точек
удовлетворяет аксиомам инцидентности.

4) Докажите, что в пространстве, удовлетворяющем аксиомам инцидентности
и между двумя точками A и B бесконечно
между ними много точек.

Индукционные доказательства: Введение

Индукция
Доказательства: Введение
(стр.
1 из 3)

Разделы: Введение, Примеры
где не удается индукция, примеры работы


Если вы читаете это
модуль, то вы, вероятно, только что рассмотрели индукцию в своем классе алгебры,
и вы чувствуете себя немного не в своей тарелке.Если ты что-нибудь
как и я, у вас те же мысли, что и у меня: «Разве ты не можешь доказать
все что угодно есть
правда, если вы предположите, что , в первую очередь, это правда? Что осталось
чтобы доказать, если вы уже предположили? Разве это не обман? »

Ну …

Во-первых, не злись
у вашего инструктора. Для него индукция имеет смысл, и он, честно говоря,
думает, что он ясно объяснил это.Когда я взял это, я знал, что у меня было
хороший профессор, так что я знаю, что получил «хороший» урок. Но я еще
не доверял индукции. Я постараюсь забрать там, где оставил ваш инструктор
выключить и заполнить некоторые отверстия.

Индукционные доказательства имеют четыре
компоненты: (1) то, что вы хотите доказать, (2) начальный шаг (обычно
«пусть н
= 1 «), (3)
шаг допущения («пусть n
= k «),
и (4) ступень индукции («пусть n
= k + 1 «).Вот мысли:
Авторские права Элизабет
Stapel 2000-2011 Все права защищены

Вы работали с
некоторые числа и заметили что-то, что кажется закономерным. К
используйте стандартный пример, допустим, вы заметили, что когда вы
сложите все числа от 1
к n
(то есть 1
+ 2 + 3 + 4 + … + n ),
вы получаете сумму, равную
( n ) ( n +1) / 2 .То есть для каждого числа, которое вы проверили, вы получите

Для удобства мы
назовите эту формулу «(*)»,
или «звезда». Вы хотели бы знать, если (*)
верно для всех целых чисел, но вы, очевидно, не можете проверить каждое
целое число, поскольку целые числа никогда не заканчиваются. Вы только знаете, что это
верно для относительно небольшого числа чисел, которые вы на самом деле проверили. Конечно,
сложение всех этих чисел быстро становится утомительным, так что вы получите на самом деле
как для (*)
работать! Но использовать (*)
для любого номера вы должны каким-то образом доказать, что (*)
работает везде.Доказательства индукции позволяют доказать, что формула
работает «везде» без необходимости показывать на самом деле
что он работает везде (делая бесконечное множество дополнений).

Итак, у вас есть первая часть
доказательства индукции, формула, которую вы хотите доказать:

    (*)
    Для всех натуральных чисел n ,
    1 + 2 + 3 + 4 + … + n = ( n ) ( n +1) / 2

Но есть (*)
когда-либо правда где угодно? Если места нет, то любое
конкретный номер, для которого (*)
известно, что это правда, то продолжать нет смысла.Так что вы
проделайте вторую часть, которая должна показать, что (*)
действительно верно в каком-то конкретном месте:

    Пусть н
    = 1. Тогда
    1 + 2 + 3 + 4 + … + n
    на самом деле всего 1;
    то есть:

    Тогда получаем 1
    = 1, поэтому (*)
    верно на n
    = 1.

Там; мы показали это
(*)
работает в каком-то конкретном месте.Но работает ли это где-нибудь еще? Хорошо,
это было нашей проблемой в первую очередь: мы знаем, что это работает в нескольких
мест, но нам нужно доказать, что (*)
работает везде , и мы никогда не сделаем этого, доказав один случай на
время. Итак, нам нужны третья и четвертая части доказательства индукции.
Третья часть — это предположительная часть:

    Пусть н
    = к .

    Предположим, что для n
    = к , (*)
    работает; то есть предположим, что:

Это не то же самое, что
вторая часть, где мы назвали фактическое место, где (*)
работал.В этой части просто говорится: «Предположим, что (*)
работает, где-то там, в космосе, я не говорю где, я не могу
даже знают, где ; просто где-то «. А вы думаете» Так
что? »Вот что: четвертый шаг. Если мы сможем доказать, при условии
(*) работает на
н
= k
, что (*)
затем работает на n
= k + 1 (что
То есть, если он работает на на каком-то месте, то он также должен работать на на следующем
место), то, поскольку мы знаем о определенном месте ( n
= 1) где (*)
работает, мы докажем, что (*)
работает везде:

    Пусть
    н.
    = к + 1.
    Тогда
    1
    + 2 + 3 + 4 + … + к + ( к + 1)
    [the
    левая часть (*)]
    = [1 + 2 + 3 + 4 + … + k ] + k + 1 [из
    часть третья]
    = [ ( k ) ( k +1) / 2 ] + k
    + 1
    [наш
    предположение]
    = [ ( k ) ( k +1) / 2 ] + 2 ( k +1) / 2 [общий
    знаменатель]
    = ( к ) ( к +1) +2 ( к +1) / 2 [добавление
    фракции]
    = ( к +2) ( к +1) / 2 [упрощение]
    = (( к +1) +1) ( к +1) / 2 [пересчитать
    дюйм « к
    + 1 «форма]

Эта последняя строка правая
сторона (*).Другими словами, если предположить, что (*)
работает как какой-то безымянный безликий номер
k , тогда мы можем
показать (используя это предположение), что (*)
работает по следующему номеру, к
+ 1. И мы уже
знать номер, где (*)
работает! Поскольку мы показали, что (*)
работает на n
= 1, предположение
и шаги индукции говорят нам, что (*)
затем работает на n
= 2, а затем по
индукционный
(*)
работает на n
= 3, а затем по
индукционный
, (*)
работает на n
= 4 и т. Д.В
шаги предположения и индукции позволяют нам совершить скачок от «It
работает здесь и там «на» Работает везде! »
как домино: вместо того, чтобы сбивать каждого по отдельности, вы говорите
«Если я смогу сбить одного из них, то он снесет
следующий, затем следующий, и, в конце концов, все; и посмотри!
Я могу сбить этого первого прямо здесь. «

Верх
| 1 | 2 | 3
| Вернуться к указателю Далее
>>

Цитируйте эту статью
как:

Стапель, Елизавета.«Индукционные доказательства: Введение». Пурпурная математика . Имеется в наличии
из
https://www.purplemath.com/modules/inductn.htm .
Доступ [Дата] [Месяц] 2016 г.


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

Математическая индукция — это особый способ доказательства.В нем всего 2 ступени:

  • Шаг 1. Покажите, что это верно для первого
  • Шаг 2. Покажите, что если любое истинно, то следующее истинно

Тогда все верны

Вы слышали об «эффекте домино»?

  • Шаг 1. Первые падения домино
  • Шаг 2. Когда выпадает любого домино, выпадает следующих домино

Итак… все домино упадут!

Так работает математическая индукция.

В мире чисел мы говорим:

  • Шаг 1. Покажите, что это верно для первого случая, обычно n = 1
  • Шаг 2. Покажите, что если n = k верно, то n = k + 1 также верно

Как это сделать

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

Шаг 2 лучше всего выполнить так:

  • Предположим, что верно для n = k
  • Докажите, что истинно для n = k + 1 (мы можем использовать случай n = k как факт .)

Это все равно что сказать «ЕСЛИ мы можем заставить домино упасть, упадет ли следующая?»

Шаг 2 часто может быть сложным , нам, возможно, придется использовать творческие уловки, чтобы заставить его работать!

Как в этом примере:

Пример: 3

n −1 делится на 2?

Это правда? Давайте узнаем.

1. Покажите, что это верно для n = 1

3 1 −1 = 3−1 = 2

Да 2 делится на 2.Это было просто.

3 1 −1 верно

2. Предположим, что это верно для n = k

3 k −1 верно

(Погодите! Откуда мы это знаем?
Мы этого не делаем!
Это предположение … что мы рассматриваем
как факт для остальной части этого примера)

Теперь докажем, что 3 k + 1 −1 делится на 2

3 k + 1 также 3 × 3 k

Затем разделите 3 × на 2 × и 1 ×

И каждое из них кратно 2

Потому что:

  • 2 × 3 k делится на 2 (мы умножаем на 2)
  • 3 k −1 верно (мы сказали, что в предположении выше)

Итак:

3 k + 1 −1 верно

СДЕЛАНО!

Вы видели, как мы использовали случай 3 k −1 как истинный , хотя мы этого и не доказали? Это нормально, потому что мы полагаемся на Domino Effect

… мы спрашиваем , если упадет любое домино, упадет ли следующий ?

Итак, мы принимаем это как факт (временно), что домино « n = k » падает (т.е. 3 k −1 верно), и посмотрим, означает ли это « n = k + 1 ». «Домино тоже упадет.

Уловки

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

Распространенный трюк — переписать случай n = k + 1 на 2 части:

  • одна часть представляет собой случай n = k (который предполагается верным)
  • затем можно проверить другую часть, чтобы убедиться, что она также верна

Мы сделали это в примере выше, а вот еще один:

Пример: сложение нечетных чисел

1 + 3 + 5 +… + (2n − 1) = n 2

1. Покажите, что это верно для n = 1

1 = 1 2 верно

2. Предположим, что это верно для n = k

1 + 3 + 5 + … + (2k − 1) = k 2 верно
(Предположение!)

Теперь докажите, что это верно для «k + 1»

1 + 3 + 5 + … + (2k − 1) + (2 (k + 1) −1) = (k + 1) 2 ?

Мы знаем, что 1 + 3 + 5 +… + (2k − 1) = k 2 (предположение выше), поэтому мы можем сделать замену для всех членов, кроме последнего:

к 2 + (2 (k + 1) −1) = (k + 1) 2

Теперь разверните все термины:

к 2 + 2 к + 2 — 1 = к 2 + 2 к + 1

И упростить:

к 2 + 2k + 1 = к 2 + 2k + 1

Они такие же! Так что это правда.

Итак:

1 + 3 + 5 +… + (2 (k + 1) −1) = (k + 1) 2 верно

СДЕЛАНО!

Ваша очередь

А теперь еще два примера , на которых вы можете попрактиковаться.

Сначала попробуйте сами, а затем посмотрите наше решение ниже.

Пример: треугольные числа

Треугольные числа — это числа, которые могут образовывать треугольный точечный узор.

Докажите, что n-ое треугольное число равно:

Т п = п (п + 1) / 2

Пример: сложение чисел куба

Числа куба — это кубы натуральных чисел

Докажите, что:

1 3 + 2 3 + 3 3 +… + n 3 = ¼n 2 (n + 1) 2

. . . . . . . . . . . . . . . . . .

Пожалуйста, не читайте решения, пока не попробуете сами, это единственные вопросы на этой странице, над которыми вы можете попрактиковаться!

Пример: треугольные числа

Докажите, что n-ое треугольное число равно:

Т п = п (п + 1) / 2

1. Показать, что это верно для n = 1

T 1 = 1 × (1 + 1) / 2 = 1 верно

2. Предположим, что это верно для n = k

T k = k (k + 1) / 2 Верно (предположение!)

Теперь докажите, что это верно для «k + 1»

Т к + 1 = (к + 1) (к + 2) / 2?

Мы знаем, что T k = k (k + 1) / 2 (предположение выше)

T k + 1 имеет дополнительный ряд из (k + 1) точек

Итак, T k + 1 = T k + (k + 1)

(к + 1) (к + 2) / 2 = к (к + 1) / 2 + (к + 1)

Умножьте все члены на 2:

(к + 1) (к + 2) = к (к + 1) + 2 (к + 1)

(к + 1) (к + 2) = (к + 2) (к + 1)

Они такие же! Так что правда .

Итак:

T k + 1 = (k + 1) (k + 2) / 2 истинно

СДЕЛАНО!

Пример: сложение чисел куба

Докажите, что:

1 3 + 2 3 + 3 3 + … + n 3 = ¼n 2 (n + 1) 2

1. Покажите, что это верно для n = 1

1 3 = ¼ × 1 2 × 2 2 верно

2. Предположим, что это верно для n = k

1 3 + 2 3 + 3 3 + … + k 3 = ¼k 2 (k + 1) 2 верно (предположение!)

Теперь докажите, что это верно для «k + 1»

1 3 + 2 3 + 3 3 + … + (k + 1) 3 = ¼ (k + 1) 2 (k + 2) 2 ?

Мы знаем, что 1 3 + 2 3 + 3 3 +… + k 3 = ¼k 2 (k + 1) 2 (предположение выше), поэтому мы можем заменить все, кроме последнего члена:

¼k 2 (k + 1) 2 + (k + 1) 3 = ¼ (k + 1) 2 (k + 2) 2

Умножьте все члены на 4:

к 2 (к + 1) 2 + 4 (к + 1) 3 = (к + 1) 2 (к + 2) 2

Все термины имеют общий множитель (k + 1) 2 , поэтому его можно отменить:

к 2 + 4 (к + 1) = (к + 2) 2

И упростить:

к 2 + 4 к + 4 = к 2 + 4 к + 4

Они такие же! Так что это правда.

Итак:

1 3 + 2 3 + 3 3 + … + (k + 1) 3 = ¼ (k + 1) 2 (k + 2) 2 верно

СДЕЛАНО!

Исчисление

— что означает «доказать по индукции»?

Доказательство по индукции означает, что вы доказываете что-то для всех натуральных чисел, сначала доказывая, что это верно для $ 0 $, и что если оно верно для $ n $ (или иногда для всех чисел до $ n $), то оно верно и для $ n + 1 $.

Пример:

Доказательство того, что $ 1 + 2 + 3 + \ dots + n = n (n + 1) / 2 $:

  • Для $ n = 0 $ в левой части указана пустая сумма, которая по определению равна $ 0 $. Справа у вас $ 0 (0 + 1) / 2 = 0 $. Таким образом, уравнение верно для $ n = 0 $.

  • Предположим, что формула верна для $ n $. Тогда мы можем доказать это для $ n + 1 $ следующим образом:

    По предположению, $ 1 + 2 + \ dots + n + (n + 1) = n (n + 1) / 2 + (n + 1) $. Но правая часть легко вычисляется и равна $ (n + 1) ((n + 1) +1) / 2 $.

Теперь, поскольку мы доказали это для $ 0 $ и для $ n + 1 $, предполагая, что это верно для $ n $, мы доказали это индукцией для всех $ n $.

Первая часть называется индукционным пуском, а вторая часть — индукционной ступенью.

Теперь, конечно, вы хотите знать:

Представьте, что вы хотите знать, верно ли это для $ n = 5 $. Конечно, вы можете просто вычислить это напрямую, но предположим, что вы забыли, как это вычислить, и все, что вы помните, это то, что вы доказали это для $ n = 0 $ и что если это верно для $ n $, то оно верно и для $ n + 1 $.

Хорошо, вы знаете, что это верно для $ n = 0 $.

Если это верно для $ n = 0 $, то с помощью шага индукции, который вы доказали, это верно для $ n + 1 = 1 $

Но если это правда для $ n = 1 $. их по индукции верно при $ n + 1 = 2 $.

Но если это правда для $ n = 2 $. их по шагу индукции верно для $ n + 1 = 3 $.

Но если это правда для $ n = 3 $. их по индукции верно при $ n + 1 = 4 $.

Но если это правда для $ n = 4 $. их по шагу индукции верно для $ n + 1 = 5 $.

Таким образом, вы доказали это для $ n = 5 $.

Легко видеть, что это позволяет вам механически сформулировать доказательство для любого отдельного $ n $, и, таким образом, очевидно, что оно должно быть истинным для всех $ n $.

Доказательство неравенства с помощью индукции

Доказательство неравенства с помощью индукции

Доказательство
Неравенство по индукции


Ответы:

1 . а . P (3): n 2
= 3 2 = 9 и 2 n + 3 = 2 (3)
+ 3 = 9

n 2
= 2 n + 3, т.е. P (3) верно.

б . P ( k ): k 2 > 2 k + 3

с . п. ( к + 1): ( к
+ 1) 2 > 2 ( к + 1)
+ 3

д . Индуктивная гипотеза : P ( k )
= к 2 > 2 к
+ 3 предполагается.

Индуктивный ступень : Для
п. ( к + 1),

      > (2 к
      + 3) + 2 к + 1 по
      Индуктивная гипотеза

      > 4 к + 4

      > 4 ( k + 1) коэффициент
      выход k + 1 с двух сторон

    к + 1 >
    4

    к
    > 3

    Вывод: Очевидно, что любое k больше или равно
    3 составляет последнее уравнение, k > 3, верно.В
    индуктивный шаг, вместе с тем, что P (3) верно,
    приводит к выводу, что для всех n > 3,
    n 2 > 2 n
    +3 верно.

2 . Докажите, что 2 n < n !
для n > 4.

    Решение:

    Базовый шаг : 2 4 = 16, 4! = 24,
    и 16 <24, поэтому P (4) верно.

    Индуктивная гипотеза : Предположим, что для всех k >
    n
    , P ( k ) = 2 k
    < к! верно.

    Индуктивный шаг : Если верно для P ( k ),
    тогда верно для P ( k + 1).Докажи это
    П ( к + 1): 2 к +1
    <( к + 1) !. Умножьте обе части индуктивной гипотезы
    на 2, чтобы получить, для k > 4,

      2 x 2 k = 2 k +1
      <2 ( к !) <( к + 1) x ( к !)
      (= ( k + 1)!)
      2 x 2 k <2 < k + 1 (разделить
      все сроки по к!)
      к
      !

      Поскольку мы предполагаем, что наша исходная гипотеза верна, дробь 2 k / k !
      будет числом меньше 1, а первый член (выделенный красным) будет
      следовательно, будет меньше 2.Аналогично для всех k >
      4, 2 < k + 1 верно.

    Мы доказали, что 2 n +1
    <( n + 1)! для n > 4, следовательно, P ( n )
    верно для всех n > 4

Доказательств — Математическая индукция (CSCI 2824, весна 2015 г.)

В этой серии заметок мы переходим к

  1. Доказательства различных утверждений

  2. Прошу исправить некоторые из наших доказательств.

  3. Практикуйтесь в доказательстве теорем, выражая свои аргументы в сжатой и логически последовательной форме.

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

Эта лекция соответствует разделу 2.3 книги Энсли и Кроули.

Математическая индукция: общий принцип

Математическая индукция — очень распространенный метод доказательства
свойства натуральных чисел (и других дискретных структур, таких как
множества, отношения и деревья, которые мы очень скоро изучим).

Вот видео падающих домино: Щелкните здесь !.

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

Мы хотим доказать, что каждое домино упадет. Вот как можно спорить:

  • Базовый вариант: Первый домино падает (мы его пнули, так оно и падает).

  • Индуктивный шаг:
    Всякий раз, когда пронумерованный домино падает
    (или все домино с номером 1 упадут),
    затем его преемник пронумерован, также падает.

  • Следовательно, делаем вывод, что все домино выпадут.

Приведенный выше аргумент является сутью индукции. Чтобы доказать свойство над всеми натуральными числами, мы можем рассуждать следующим образом:

  • Свойство истинно для (первое натуральное число).

  • Если свойство истинно для некоторого натурального числа
    (или если свойство истинно для всех натуральных чисел от до ),
    тогда это верно для натурального числа.

Доказательства слабой индукции

Слабая индукция предлагает простой способ доказательства свойства
для всех натуральных чисел. Т.е.

Доказательство с помощью слабой индукции выполняется в три простых шага!

Пример 1

Индукция может быть действительно полезной для угадывания и доказательства замкнутой формы последовательностей. Рассмотрим простой:

Есть.
Следовательно, вот наше предположение :. Как мы это докажем?

Иск: .

Пример 2

Теорема. Сумма первых чисел
.

Доказательство индукцией (точно так же, как мы сделали для домино)

Пример 3

Попробуем последовательность.

Сначала мы догадаемся, какой может быть закрытая форма, записав первую
несколько терминов:

.

Иск: .

Сильное индукционное доказательство: убедительный пример

С помощью слабой индукции мы доказываем, что число удовлетворяет, предполагая, что (его непосредственный предшественник) удовлетворяет.Это не всегда может дать
простейшее доказательство.

Сначала несколько определений:

Функции пола и потолка

В качестве примеров, тогда как. Для отрицательных чисел это немного противоречит интуиции:
тогда как .

Учитывайте повторение.

Вот результат повторения нескольких значений.

Некоторые из вас могут распознать шаблон (он очень важен для CS). Вот пример : для с.

Теперь мы можем попробовать доказать это по индукции. Сначала воспользуемся слабой индукцией.

Теорема применима только к натуральным числам. Мы справляемся с этим, просто позволяя базовому случаю индукции начинаться с.

Доказательство слабой индукцией (неудача…)

Базовый случай Для, мы это проверяем.

Индуктивная гипотеза: .

Это нелегко доказать, и на самом деле это неправда. Это потому, что зависит от нашего, а не от него.
предыдущие последовательности.

Доказательство сильной индукцией

Сильная индукция отличается от слабой в индуктивной гипотезе.

Возвращаясь к домино, мы предполагаем по слабой индукции, что домино падает, и доказываем, что то же самое.
Используя сильную индукцию, мы предполагаем, что все пронумерованные домино выпадают, и доказываем, что в этом случае также выпадают.

Претензия: Для всех, если,
тогда .

Для полноты, вот доказательство побочного утверждения.

Дополнительное требование: Для всех натуральных чисел, если оно четное, то.

Доказательство индукцией

Доказательство индукцией


Математический факультет Университета штата Иллинойс

MAT 305: Темы комбинаторики для K-8
Учителя



Здесь мы плохо рассуждаем и объясняем полезное оправдание
метод называется Доказательство индукцией . Процесс
описывается с использованием четырех шагов, краткое
приводится краткое изложение, а также некоторые практические
представлены проблемы.

Мы проиллюстрируем процесс доказательства индукцией , чтобы показать
что

(Я)

Процесс

Шаг 1. Убедитесь, что желаемый результат сохраняется для n = 1.

Здесь, когда 1 заменяется на n как в левой, так и в правой части
выражения в (I) выше, результат равен 1.В частности

. Этот
завершает шаг 1.

Шаг 2: Предположим, что желаемый результат верен для n = k.

В нашем примере это означает, что мы предполагаем, что сумма первых k
положительные целые числа.
Будет полезно показать это как

.

(II)

Шаг 2 завершен.

Шаг 3. Используйте предположение из шага 2, чтобы показать, что результат
выполняется для n = (k + 1).

То есть мы хотим это показать.
Другими словами, покажите, что предположение результата для n = k влечет за собой
результат для n = (k + 1).

Здесь мы опираемся на уравнение, представленное в (II):

Если, добавляя
(k + 1) в каждую сторону гарантирует, что

(III)

Левая часть (III) — это просто расширение выражения
, это
сумма первых (k + 1) натуральных чисел.

Нам осталось показать, что правая часть (III) эквивалентна
, какие наши
формула говорит нам, что это правильная сумма.

Записываем правую часть (III) с общим знаменателем:

.

(IV)

Теперь сложите числители и выразите через общий знаменатель:

.

(V)

В числителе (V) k + 1 является общим для обоих членов, поэтому мы можем
множите числитель, получая эквивалентную форму:

(VI)

Выражение (VI) — это именно тот результат, который мы искали.

Шаг 4: Подведите итоги своей работы.

Мы показали по индукции, что сумма первых n положительных
целые числа могут быть представлены выражением.

Уравнение имеет
практическое применение в любое время, когда мы ищем суммы последовательных положительных
целые числа. Например, теперь мы можем использовать результат, чтобы сделать вывод, что
. Мы также можем
используйте результат, чтобы показать, что, например,.

Сводка

Индукция
процесс основан на эффекте домино.Если мы сможем показать, что результат
верно от k-го до (k + 1) -го случая, и мы действительно можем показать это
верно для первого случая (k = 1), мы можем связать цепочку
Выводы: истина для k = 1 влечет истину для k = 2, истина для k = 2
следует истина для k = 3 и т. д. Нажатие первого домино вызывает все
оставшихся домино выпадают подряд.

Практика

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *