Докажите что для любого натурального n
Докажите, что для любого натурального n найдутся n подряд идущих натуральных чисел, среди которых ровно одно простое.
Решение
Согласно задаче 34990 найдутся n подряд идущих составных чисел. Рассмотрим наименьшее простое число p, большее всех этих чисел (такое существует согласно задаче 30410). Тогда числа p – n + 1, p – n + 2, . p – 1, p – искомые.
Источники и прецеденты использования
книга | |
Автор | Алфутова Н.Б., Устинов А.В. |
Год издания | 2002 |
Название | Алгебра и теория чисел |
Издательство | МЦНМО |
Издание | 1 |
глава | |
Номер | 3 |
Название | Алгоритм Евклида и основная теорема арифметики |
Тема | Алгебра и арифметика |
параграф | |
Номер | 1 |
Название | Простые числа |
Тема | Основная теорема арифметики. Разложение на простые сомножители |
задача | |
Номер | 03.013 |
Проект осуществляется при поддержке и .
Докажите что для любого натурального n
Пусть дана последовательность пронумерованных утверждений: Утв 1 , Утв 2 , Утв 3 , . Утв k , Утв k+1 , . (конечная или бесконечная). Мы сможем доказать все эти утверждения, если докажем, что:
1) Утв 1 — истинно;
2) Если истинно Утв k , то истинно и Утв k+1 (для любого натурального номера k ).
Действительно, в этом случае истинно первое утверждение (п.1), тогда по п.2 истинно и второе, а значит, и третье, и т.д.
Этот метод доказательства последовательности утверждений называется методом математической индукции . Он состоит из двух вышеуказанных этапов. Первый из них называется база индукции, а второй — переход индукции или шаг индукции .
1. Докажите тождество: 1 + 3 + 5 + … + (2 n − 1) = n ² для любого натурального n .
Эти тождества образуют последовательность утверждений, занумерованных числом n , а именно:
Утв 1 : 1 = 1²
Утв 2 : 1 + (2·2 − 1) = 1 + 3 = 2² = 4
Утв 3 : 1 + 3 + 5 = 3²
.
Утв k : 1 + 3 + 5 + … + (2 k − 1) = k ²
Утв k+1 : 1 + 3 + 5 + … + (2·( k + 1) − 1) = ( k + 1)²
.
База индукции: докажем первое утверждение, то есть что 1 = 1². Но это очевидно.
Шаг индукции: докажем, что из Утв k следует Утв k+1 . Пусть уже доказано, что 1 + 3 + 5 + … + (2 k − 1) = k ². Надо доказать, что тогда 1 + 3 + 5 + … + (2·( k + 1) − 1) = ( k + 1)². Запишем: 1 + 3 + 5 + … + (2 k − 1) + (2·( k + 1) − 1) = k ² + (2 k + 1) = ( k + 1)². Здесь первое равенство выполняется, поскольку верно Утв k .
Таким образом, доказаны база и шаг индукции, а значит, и требуемое Утв n : 1 + 3 + 5 + … + (2 n − 1) = n ² доказано для любого натурального n .
2. Известно, что x + 1 / x — целое число. Докажите, что при любом целом n число x n + 1 / x n — также целое.
Сначала докажем это утверждение при n = 0. Но x 0 + 1 / x 0 = 1 + 1 = 2 — целое, поэтому это утверждение очевидно. Если число n отрицательно, и n = — m , где m — натуральное, то x n + 1 / x n = x − m + 1 / x − m = x m + 1 / x m . Поэтому достаточно доказать утверждение для натуральных n .
Применим метод математической индукции аналогично тому, как это сделано в предыдущей задаче.
База индукции: докажем, что если x + 1 / x — целое, то x ¹ + 1 / x ¹ — тоже. Но это очевидно, так как x ¹ + 1 / x ¹ = x + 1 / x .
Шаг индукции: Пусть известно (то есть доказано на предыдущих шагах индукции), что x + 1 / x , x ² + 1 / x ² , x ³ + 1 / x ³ , …, x k − 1 + 1 / x k − 1 , x k + 1 / x k — целые числа. Докажем, что тогда x k + 1 + 1 / x k + 1 — тоже целое. Для этого запишем: ( x k + 1 / x k )·( x + 1 / x ) = x k + 1 + 1 / x k − 1 + x k − 1 + 1 / x k + 1 = ( x k + 1 + 1 / x k + 1 ) + ( x k − 1 + < / 1 < x k − 1 >). Отсюда находим, что x k + 1 + 1 / x k + 1 = ( x k + 1 / x k )·( x + 1 / x ) − ( x k − 1 + 1 / x k − 1 ). Первое слагаемое в правой части этого равенства является произведением двух целых чисел по предположению, а значит, и само является целым. Второе слагаемое — тоже целое по предположению. Значит, их сумма — целое число. Тогда и в левой части равенства стоит целое число, что и требовалось доказать.
Упражнение. Как найти какое-нибудь число x , для которого x + 1 / x = k , где k — заданное целое число? При каких целых k это можно сделать?
3. Докажите неравенство 2 n > n для произвольного натурального n .
Решение.
База индукции. Докажем, что 2¹ > 1. Но это очевидно.
Шаг индукции. Пусть известно, что 2 k > k . Докажем, что тогда 2 k + 1 > k + 1. Запишем 2 k + 1 = 2·2 k > 2· k > k + 1, если k > 1. Первое неравенство в этой цепочке вытекает из предположения о том, что 2 k > k .
4. Найдите все натуральные n , при которых 2 n не больше, чем n ².
Ясно, что при n = 1 утверждение неверно, так как 2·1>1 2 . А вот при n = 2, n = 3, n = 4 оно уже верно (убедитесь в этом самостоятельно). Причем с увеличением числа n увеличивается и разность между числами n ² и 2 n . Это наводит на мысль, что 2 n ≤ n ² при всех натуральных n , бóльших единицы. Теперь строго докажем это по индукции.
База индукции: n = 2. Надо доказать, что 2·2 ≤ 2 2 . Но это очевидно.
Шаг индукции. Пусть известно, что 2 k ≤ k ². Докажем, что 2( k + 1) ≤ ( k + 1)². Запишем ( k + 1)² = k ² + 2 k + 1 ≥ 2 k + 2 k + 1 = 2( k + 1) + 2 k − 1 ≥ 2( k + 1), если 2 k − 1 ≥ 0, в том числе при любом натуральном k , что и требовалось доказать.
Замечание. Эту задачу можно решить и без использования метода математической индукции. Пусть n ≥ 2. Домножим обе части этого неравенства на n (это можно сделать, так как если n ≥ 2, то n > 0). Получим n ² ≥ 2 n , что и требовалось доказать.
5. В прямоугольнике размера 3× n стоят фишки трех цветов, по n штук каждого цвета. Докажите, что можно переставить фишки в каждой строке так, чтобы в любом столбце были фишки всех цветов.
Решение. Докажем это утверждение индукцией по n .
База индукции: n = 1. В прямоугольнике размера 3×1 находятся три фишки, каждая своего цвета. Тогда требование задачи уже выполнено, и вообще ничего переставлять не надо.
Шаг индукции. Пусть для любого прямоугольника размера 3× k (с указанным набором фишек) требуемая перестановка существует. Докажем, что она существует и для любого прямоугольника размера 3× (k + 1). Сначала переставим фишки так, чтобы в последнем, ( k + 1)-м столбце все фишки были разноцветными. Ясно, что в оставшейся части прямоугольника (размера 3× k ) находятся по k фишек каждого цвета. Применив наше предположение, расставим в этой части фишки требуемым образом. В результате в каждом из столбцов от первого до k -го фишки разноцветные по предположению, а в последнем столбце — по построению.
6. Несколько прямых делят плоскость на части. Докажите, что эти части можно раскрасить в два цвета так, что любые две граничащие (то есть имеющие общую сторону) части будут раскрашены в разные цвета.
Решение. Докажем это утверждение индукцией по количеству прямых.
База индукции. Пусть на плоскости проведена всего одна прямая, которая делит эту плоскость на две части. Одну из этих частей покрасим в белый цвет, а другую — в черный. Тогда требование условия будет выполнено.
Шаг индукции. Пусть на плоскости проведено k прямых, и части плоскости раскрашены в черный и белый цвета требуемым образом. Проведем ( k + 1)-ую прямую. Все части плоскости по одну сторону от этой новой прямой перекрасим в противоположные цвета, а по другую сторону оставим все без изменений (см. рисунок). Убедитесь, что в этом случае части плоскости будут раскрашены требуемым образом.
7. Докажите, что 1· 1! + 2 · 2! + . + n · n ! = ( n + 1)! − 1 для всех натуральных n (здесь n ! = 1·2·3·. · n ).
Решение. База индукции. Надо доказать, что 1·1! = (1 + 1)! − 1. Это верно, так как 1! = 1, 2! = 2.
Шаг индукции. Пусть доказано, что 1· 1! + 2 · 2! + . + k · k ! = ( k + 1)! − 1. Докажем, что тогда 1· 1! + 2 · 2! + . + k · k ! + ( k + 1)·( k + 1)! = ( k + 2)! − 1. Запишем 1· 1! + 2 · 2! + . + k · k ! + ( k + 1)·( k + 1)! = ( k + 1)! − 1 + ( k + 1)·( k + 1)! = ( k + 1)!·(1 + k + 1) − 1 = ( k + 1)!·( k + 2) − 1 = ( k + 2)! − 1. Здесь мы пользовались тем, что ( k + 1)!·( k + 2) = ( k + 2)! (убедитесь, что это следует из определения числа ( k !)).
8. Для произвольного натурального n и вещественного x > -1 докажите неравенство Бернулли : (1 + x ) n ≥ 1 + nx .
Решение. Докажем это утверждение индукцией по n .
База индукции: n = 1. Надо доказать, что (1 + x )¹ ≥ 1 + 1· x . Но это очевидно.
Шаг индукции. Пусть доказано, что (1 + x ) k ≥ 1 + kx . Докажем, что тогда (1 + x ) k + 1 ≥ 1 + ( k + 1)· x . Запишем (1 + x ) k + 1 = (1 + x ) k ·(1 + x ) ≥ (1 + kx )·(1 + x ) = 1 + kx + x + kx ² ≥ 1 + ( k + 1)· x , что и требовалось доказать. Здесь мы воспользовались тем, что при любом натуральном k и любом действительном x имеем kx ² ≥ 0, а также предположением о том, что (1 + x ) k ≥ 1 + kx .
9. Любую ли сумму из целого числа рублей, большего семи, можно уплатить без сдачи денежными купюрами по 3 и 5 рублей? Почему?
Решение. Ясно, что 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5. Прибавляя к 8 нужное количество троек, можем получить любое число, делящееся на 3 с остатком 2. Прибавляя тройки к 9, получим все числа, делящиеся на 3 без остатка. А прибавляя тройки к 10, получим все числа, делящиеся на 3 с остатком 1. Проведите строгое доказательство самостоятельно. Для произвольного натурального n ≥ 8 укажите способ его представления в виде суммы троек и пятерок в зависимости от его остатка при делении на 3, основываясь на вышеизложенных соображениях.
10. Коля Васин при помощи метода математической индукции смог доказать, что в любом табуне все лошади одной масти. Для этого он провел такие рассуждения: «Если есть только одна лошадь, то она своей масти, так что база индукции верна. Для перехода предположим, что есть n лошадей (с номерами от 1 до n ). Пусть уже доказано, что в любом табуне из ( n — 1) лошади все лошади одной масти. Значит, в нашем табуне все лошади с номерами от 1 до ( n — 1) одинаковой масти. По тем же соображениям лошади с номерами от 2 до n одинаковой масти. Но лошади с номерами от 2 до ( n — 1) не могут менять свою масть в зависимости от того, как они сгруппированы, — это ведь лошади, а не хамелеоны. Поэтому все n лошадей должны быть одинаковой масти». Есть ли ошибка в этом рассуждении, и если есть, то какая?
Ответ. Ну конечно же есть!
Решение. «Переход» индукции, предложенный Колей, не позволит нам доказать утверждение даже для табуна из двух лошадей. Первая лошадь своей масти, вторая — тоже. Однако никаких лошадей с промежуточными номерами нет. Поэтому и между нашими двумя лошадьми, вообще говоря, нет ничего общего.
Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! | | | |
Докажите что для любого натурального n
Докажите, что для любого натурального n 4 n + 15 n – 1 делится на 9.
Решение
4 n – 1 + 15n = 3(4 n–1 + 4 n–2 + . + 1 + 5n), а число 4 n–1 + 4 n–2 + . + 1 + 5n ≡ 1 + 1 + . + 1 + 5n = 6n ≡ 0 (mod 3).
Источники и прецеденты использования
книга | |
Автор | Алфутова Н.Б., Устинов А.В. |
Год издания | 2002 |
Название | Алгебра и теория чисел |
Издательство | МЦНМО |
Издание | 1 |
глава | |
Номер | 1 |
Название | Метод математической индукции |
Тема | Индукция |
параграф | |
Номер | 2 |
Название | Тождества, неравенства и делимость |
Тема | Индукция (прочее) |
задача | |
Номер | 01.023 |
Проект осуществляется при поддержке и .
Метод математической индукции для чайников
Метод полного перебора конечного числа случаев, исчерпывающих все возможности, называется полной индукцией. Этот метод имеет крайне ограниченную область применения в математике, так как обычно математические утверждения касаются бесконечного множества объектов (например, натуральных чисел, простых чисел, квадратов и т.п.) и перебрать их невозможно.
Существует метод рассуждений, который позволяет заменить неосуществимый бесконечный перебор доказательством того, что если утверждение истинно в одном случае, то оно окажется истинным и в следущем за ним случае. Этот метод носит название математической индукции (или рассуждением от $n$ к $n+1$)
Основы метода математической индукции
В основе метода математической индукции (ММИ) лежит принцип математической индукции: утверждение $P(n)$ (где $n$ — натуральное число) справедливо при $\forall n \in N$, если:
- Утверждение $P(n)$ справедливо при $n=1$.
- Для $\forall k \in N$ из справедливости $P(k)$ следует справедливость $P(k+1)$.
Доказательство с помощью метода математической индукции проводится в два этапа:
- База индукции (базис индукции). Проверяется истинность утверждения при $n=1$ (или любом другом подходящем значении $n$)
- Индуктивный переход (шаг индукции). Считая, что справедливо утверждение $P(k)$ при $n=k$, проверяется истинность утверждения $P(k+1)$ при $n=k+1$.
Метод математической индукции применяется в разных типах задач:
- Доказательство делимости и кратности
- Доказательство равенств и тождеств
- Задачи с последовательностями
- Доказательство неравенств
- Нахождение суммы и произведения
Ниже вы найдете примеры решения задач, иллюстрирующие применение метода математической индукции, а также ссылки на полезные сайты и учебник и небольшой видеоурок по ММИ.
Полезная страница? Сохрани или расскажи друзьям
Математическая индукция: задачи и решения
Доказательство кратности и делимости
Задача 1. Докажите, что $5^n-4n+15$ делится на 16 при всех $n \in N_0$.
Задача 2. Доказать, что при любом натуральном $n$ число $a_n$ делится на $b$.
$$a_n = 2n^3+3n^2+7n, \quad b=6.$$
Задача 3. Докажите методом математической индукции: $4^ + 1$ кратно 5 для всех $n \ge 1$.
Задача 4. Используя метод математической индукции, докажите, что для любого натурального числа истинно следующее утверждение: $6^+3^+3^$ кратно 11.
Доказательство равенств и неравенств
Задача 5. Доказать равенство
Задача 6. Доказать методом математической индукции:
Задача 7. Доказать неравенство:
Задача 8. Доказать утверждение методом математической индукции:
$$ \left(1-\frac\right)\left(1-\frac\right)\left(1-\frac\right)\cdot . \cdot\left(1-\frac\right) =\frac \quad (n \ge 2). $$
Задача 9. Доказать неравенство:
$$ 2!\cdot 4! \cdot . \cdot (2n)! \gt [(n+1)!]^n \quad (n \gt 2).$$
Задача 10. Докажите методом математической индукции неравенство Бернулли: $(1+a)^n \gt 1 + a\cdot n$ для всех $n\in N$ и $a \gt -1$, $a \in R$.
Вычисление сумм
Задача 11. Доказать методом математической индукции:
Задача 12. Найдите сумму
$$1 \cdot 1! + 2 \cdot 2! + . . . + 2012 \cdot 2012! + 2013 \cdot 2013!$$
Заказать решение
Если вам нужна помощь с решением задач по любым разделам математики, обращайтесь в МатБюро. Выполняем контрольные и практические работы, ИДЗ и типовые расчеты на заказ. Стоимость задания от 60 рублей , оформление производится в Word, срок от 2 дней.
Заказать решение задач по математике легко!
Полезные ссылки о ММИ
- ММИ: краткая теория и примеры решений Страничка виртуальной школы юного математика. Разобраны примеры (в том числе для геометрии) и даны задачи для самостоятельной работы.
- Виленкин Н.Я. Индукция. Комбинаторика Классическое пособие по методу математической индукции и комбинаторике (базовые понятия и примеры задач).
- Математическая индукция. Основные определения и 10 разобранных решений.
- Николаева С.А. Метод математической индукции: методическое пособие для учителей и учащихся.
- А. Шень Математическая индукция. Пособие для школьников, разобраны 29 задач, из них 19 с полным решением.