Доказать что при каждом натуральном n число an делится на b если

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

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

Основы метода математической индукции

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

Метод математической индукции применяется в разных типах задач:

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

Математическая индукция: задачи и решения

Доказательство кратности и делимости

$$a_n = 2n^3+3n^2+7n, \quad b=6.$$

Доказательство равенств и неравенств

Задача 5. Доказать равенство

Задача 6. Доказать методом математической индукции:

Задача 7. Доказать неравенство:

Задача 8. Доказать утверждение методом математической индукции:

Задача 9. Доказать неравенство:

Вычисление сумм

Задача 11. Доказать методом математической индукции:

Задача 12. Найдите сумму

Заказать решение

Полезные ссылки о ММИ

Кратенький видеоурок о ММИ

Источник

Примеры по теме «Математическая индукция»

Пример 1. Найти сумму S _n первых n нечетных чисел:

В таких ситуациях обычно начинают рассматривать частные случаи:

S ₄ = 1 + 3 + 5 + 7= 16; S ₅ = 1 + 3 + 5 + 7 + 9 = 25.

Какой вывод можно сделать на основе этих частных случаев? В данном случае высказать гипотезу несложно:

сумма первых п нечетных чисел равна квадрату их числа, т. е. квадрату числа складываемых нечетных чисел: S _n = п 2 .

Пример 2. Пусть требуется найти

для каждого натурального п.

Рассмотрим частные случаи: S₁ = 3, S ₂ = 18.

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

S ₁=1 • 3 = 3 • 1 ·(2 • 1-1) — равенство верно.

2. Индуктивное предположение: Пусть формула

верна для некоторого произвольного k > 1.

3. Индуктивный переход. Надо доказать справедливость равенства

S _{k +1}=3 k (2 k –1) + (2 k +1)(2 k + 3) = 10 k 2 + 5 k + 3,

но нам нужно было получить

S _{k +1} = 3( k + 1)(2 k + 1) = 6 k 2 + 9 k + 3.

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

Пример 3. Доказать, что при любых натуральных п число 7 n + 12п+ 17 делится на 18.

1. При n = 1 число 7 1 + 12 • 1 + 17 = 36 кратно 18.

2. Предположим, что для некоторого натурального числа k ≥ 1 число

7 k + 12 k + 17 делится на 18.

3. Рассмотрим число 7 k +1 + 12( k + 1) + 17 и докажем, что оно кратно 18.

Мы видим, что при любом натуральном k число 6 • 12 k + 90 = 18(4 k + 5)

кратно 18. Итак, мы представили число 7 k +1 +12( k + 1) + 17 в виде разности двух чисел, каждое из которых делится на 18. Следовательно, и

само число 7 k +1 + 12( k + 1) + 17 кратно 18.

(32 > 25), значит, утверждение А(5) верно.

3. Индуктивный переход. Докажем справедливость неравенства

Запишем последнее неравенство в виде

т. е. требуемое неравенство.

Итак, согласно принципу математической индукции данное неравенство справедливо при всех натуральных n > 4.

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

В данном случае проверим наше неравенство для п = 1 и п = 2.

1. При п = 1 неравенство 4 1 > 7 • 1-5 верно. При п = 2 имеем

4 2 > 7 • 2-5 также верное неравенство.

Но при любом k ≥2 число

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

Из неравенств (1) и (3) следует неравенство

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

Замечание. В данном случае базис индукции — пункт 1 — содержит доказательство данного утверждения для первых двух натуральных чисел n = 1 и n = 2. Это связано с тем, что неравенство (2) не выполняется при k = 1, но справедливо при каждом натуральном k > 1. Поэтому, доказав данное неравенство для n = 1и n = 2, в дальнейшем рассматривались числа k ≥2.

Пример 6. Доказать, что если для n положительных чисел а_1, а₂. а _n ( n > 1) выполнено условие a ₁а₂. а _n =1, то

Предположение индукции. Пусть данное утверждение справедливо для всех

3. Индуктивный переход. Докажем, что если произведение k + 1 положительных чисел равно 1, т. е. а₁а₂. а _{k +1}= 1, то их сумма не меньше количества слагаемых:

Отметим, что если все данные числа равны между собой, то каждое из них равно 1 и неравенство (6), очевидно, выполняется. Предположим, что хотя бы одно из заданных положительных чисел меньше 1, например, 0 a _{k +1} k > 1 (если какие-то другие два числа обладают указанными свойствами, то мы просто их перенумеруем).

Рассмотрим произведение k чисел: а_1, a ₂. а _{k -1}( a _k a _{k +1}) = 1. По условию все эти числа положительны:

значит, по предположению индукции имеем

Чтобы доказать неравенство (6), перепишем неравенство (7) следующим образом:

Для доказательства неравенства (6) осталось доказать, что

Левую часть последнего неравенства можно записать так:

Тогда неравенство (8) с учетом (9) примет вид

Источник

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

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

Способ доказательства методом математической индукции заключается в следующем:

1) Начало индукции. Доказывают или непосредственно проверяют справедливость утверждения ( формулы ) для n=1;

2) Индуктивный переход. Предполагают справедливость утверждения для некоторого натурального n=k .

3) Исходя из этого предположения, доказывают справедливость утверждения для n=k+1.

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

Задачи на делимость натуральных чисел часто предлагаются на математических олимпиадах разного уровня. Многие из них легко доказываются м. м.и.

1. Проверим, если n = 1, получим 13 + 2· 1 = 3 делится на 3

2. Предположим, что делится при n = к, т. е. к3+ 2к делится на 3.

3. Докажем, что при n = к + 1 полученное выражение тоже делится на 3.

(к + 1)3+ 2(к + 1) = к3 + 3к2 + 3к + 1 + 2к + 2 = (к3 + 2к) + 3к2 + 3к + 3 делится на 3, т. к. каждое слагаемое делится на 3.

Доказать, что при любом натуральном n число

(впрочем, здесь начать можно и с n=0)

2) Пусть ak делится на 7.

3) Докажем справедливость утверждения для n=k+1 ak+1=32(k+1)+1+2(k+1)+2=32k+1 9+ 2k+2 2= (32k+1+2k+2)9-7 *2k+2=9ak-7*2k+2

2) предположим, что утверждение верно при некотором натуральном n=k, т. е. число 7k+1+82k-1 делится на 19.

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

Так как каждое слагаемое полученной суммы делится на 19, то и 7k+2+82k+1 также делится на 19. Утверждение доказано.

Доказать, что при любом натуральном n число 23+1 делится на 3n+1

1) Для n=1 число 23+1=9 делится на 31+1=9

2) Пусть утверждение верно для n=k, т. е. 23+1 делится на 3k+1.

23+1=23+1=(23)3+1=(23+1)((23)2 – 23+1) делится на 3к+2

Задачи для самостоятельного решения (прислать решения на 1,2,4)

Докажите, что при всех натуральных n

1) n3 + 11n делится на 6

5) 5·23n-2 + 33n-1 делится на 19

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

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

2) Предположим справедливость формулы для n=k, т.е.

3) докажем справедливость формулы для n=k+1

Задача Доказать, что 3n

1) Проверим справедливость утверждения для n =1. 3 ≥ 3

2) Предположим справедливость формулы для n=k, т.е. 3к

3) докажем справедливость формулы для n=k+1, т. е. 3к+1

3к+1 = 3· 3к ≥ 3() = (2 + 1)( ) = 2· 2к + 2к + 2к + к = (2к+1+ к + 1) + (2к + 2к – 1), значит, тем более 3к+1

Задача Доказать, что при n ≥ 2

2) Предположим справедливость формулы для n=k, т.е.

3) докажем справедливость формулы для n=k+1, т. е.

—

Рассмотрим выражение —= , значит, тем более

Задача 4. Вывести формулу суммы первых n нечетных чисел натурального ряда.

Замечаем, что сумма первых n нечётных чисел натурального ряда равна n2 т. е. S(n)=n2. Докажем это м. м.и.

1) для n =1 формула верна.

2) предположим, что она верна для какого-нибудь натурального n=k, т. е. S(k)= k2.

Докажем, что тогда она будет верна и для n=k+1, т. е. S(k+1)=(k+1)2

Следовательно, формула верна для всех натуральных значений n, т. е. S(n)=n2

Задача 5. Доказать, что сумма квадратов первых натуральных чисел равна

12 +22 +32 +42 +…+n2=

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

т. е. для n =1 формула верна.

2) Предположим справедливость формулы для n=k, т.е. S(k)=12+22+32+…+k2 =

3) Исходя из этого предположения докажем справедливость формулы для n=k+1

Действительно, S(k+1)=12+22+32+…+k2+(k+1)2. Сумма первых k слагаемых равна S(k)= Значит, S(k+1)=S(k)+ (k+1)2=

=

Итак, мы доказали, что формула верна для n=kМы получили ту же формулу. Следовательно, в силу м. м.и. данная формула верна для любого натурального n.

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

13+23+33+…+n3=

1) при n =1 левая часть этой формулы принимает вид 13=1 ; правая часть принимает вид . Значит, при n =1 формула верна.

2) предположим, что формула верна при n=k, т. е. верно равенство 13+23+33+…+k3 =

Докажем, что тогда эта формула верна и при n=k+1 (каким бы ни было k ), т. е. верно равенство 13+23+…+k3+(k+1)3=

Для этого заметим, что левую часть доказываемого равенства можно записать в виде (13+23+33+…+k3)+(k+1)3

Но по предположению выражение в скобках равно ,

13+23+…+k3+(k+1)3= .

Значит, доказываемая формула верна при n =1, а из её справедливости при n=k вытекает, что она верна и при n=kВ силу м. м.и. отсюда вытекает справедливость этой формулы для всех натуральных значений n.

Задача 8. Доказать, что при всех натуральных n выполняется неравенство

Доказательство:Обозначим левую часть неравенства через an.

1) начало индукции. Справедливость неравенства при n=1 очевидна.

2) индуктивный переход. Пусть ak . Надо доказать, что ak+1. А поскольку ak+1= , то нам достаточно доказать неравенство . Возведя это неравенство в квадрат и упрощая, приходим к неравенству n.

Для самостоятельного решения (по желанию)

Доказать равенства для всех натуральных n

1) 12+32+52+…+(2n-1)2=

3) 13+23+…+n3=

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

4) 3n >5n+1 при n

5) 2n-1 > n(n+1) при n

6)

Источник

Доказать что при каждом натуральном n число an делится на b если

3) Шаг индукции: докажем, что утверждение верно для n = k+1, т. е.

Пример 15. Доказать, что для любого натурального n число n 3 + 5n делится на 6.

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

(k + 1) 3 + 5(k + 1) = k 3 + 3k 2 + 3k + 1 + 5k + 5 = = (k 3 + 5k) + (3k 2 + 3k) + 6 = (k 3 + 5k) + 3k(k + 1) + 6.

Первое слагаемое в этой сумме делится на 6 по предположению, второе слагаемое тоже делится на 6, так как из чисел k, k + 1 одно обязательно чётно. Значит, вся сумма делится на 6, что и требовалось доказать.

В качестве ещё одного примера докажем теорему о числе подмножеств конечного множества.

Теорема 4. Множество, состоящее из n элементов, имеет 2 n различных подмножеств.

Доказательство. Применим индукцию по числу n. Если множество A = <а>состоит из одного элемента, то его подмножества — это 0, <а>. Их 2, поэтому теорема при n = 1 верна (база индукции). Предполагаем, что любое множество из k элементов имеет 2k подмножеств. Рассмотрим множество

Все его подмножества разделим на 2 вида. К первому виду отнесём подмножества, не содержащие ак+1. По предположению, таких подмножеств 2к. Остальные подмножества содержат ак+1, их количество также равно 2к, потому что каждое из них получается добавлением ак+1 к одному из подмножеств первого вида. Всего подмножеств множества A имеется:

Источник

Статья «Подготовка к олимпиаде»»

Докажите, что при любом натуральном n выражение n 3 + 23 n делится нацело на 6.

Докажем с помощью метода математической индукции (алгебра, 9 класс, п.29).

Утверждение верно при n = 1. Действительно, 1 3 + 23·1 = 24 и 24 делится на 6.

(k + 1) 3 + 23 (k + 1) = k 3 + 3k 2 + 3k + 1 + 23k + 23 = (k 3 + 23k) + 3k 2 + 3k + 24 = (k 3 + 23k) + 3k(k + 1) + 24.

Слагаемое ( k 3 + 23 k ) делится на 6 по предположению, слагаемое 3 k ( k + 1) также делится на 6, т.к. оно делится на 3 и на 2, ведь числа k и k + 1 являются последовательными натуральными числами, а потому одно из них чётное. Число 24 кратно 6. Так как каждое слагаемое суммы кратно 6, то и сумма кратна 6. Ч.т.д.

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

Второй способ. Дискриминанты этих уравнений равны соответственно

Если числа a , b и c неположительные, то дискриминанты больше или равны нулю и все уравнения имеют действительные корни.

Сколько нулей стоит в произведении всех натуральных чисел от 10 до 25?

Сколькими нулями оканчивается 130! = 1·2·3·…·130?

Решение. Количество нулей равно количеству множителей, кратных 5, + количество множителей, кратных 25, + количество множителей, кратных 125, т.е. 26 + 5 + 1 = 32.

Пояснение: 25 = 5·5, 125 = 5·5·5.

Известно, что 9 x 2 + 16 y 2 + 144 z 2 = 169. Найдите наибольшее возможное значение выражения 6 x – 4 y + 24 z .

Для скольких целых n число целое?

Пояснение. Преобразовывая данную дробь в виде суммы, мы фактически делили двучлен 2 n + 20 на двучлен n + 7 (алгебра, 9 класс, п.16. Некоторые приёмы решения целых уравнений).

Найти все натуральные значения n , при которых число является натуральным.

Решение. Выделим из данной дроби целую часть:

Так как число 14 имеет только четыре натуральных делителя (1; 2; 7 и 14), то данное выражение принимает натуральные значения, если 14 делится на ( n + 1), то есть при n = 1; 6 и 13. (Заметим, что равенство n + 1 = 1 в натуральных числах неразрешимо.)

Решение. ОДЗ: х ≠ 1. Используя свойство модуля | A | = |- A |, перепишем данное неравенство в виде:

Так как | A + B | ≤ | A | + | B | для любых А и В, то данное неравенство верно для любого х из ОДЗ.

Решение. x 4 + 2 x 2 + 1 = a – 7, ( x 2 + 1) 2 = a – 7.

Это уравнение не имеет корней, если a – 7 a a

Источник