2017-06-28 13:44:00
Вступление
В сегодняшней статье речь пойдёт о методе математической индукции. Этот метод используется в решении многих олимпиадных задач.
А что вообще такое индукция? Слово “индукция” применяется к различным рассуждениям, в ходе которых получают глобальные и общие выводы, опираясь при этом на ряд частных утверждений.
Для того чтобы познакомиться с упомянутым методом, попробуем решить несколько задач (более подробно – в разделе “Практика”). Но для начала рассмотрим такую задачку. Нам необходимо найти сумму всех нечётных чисел. Под этим подразумевается, что нужно определить формулу, с помощью которой мы быстро можем рассчитать требуемую сумму. Давайте сделаем это “в лоб”.
\(1=1\)
\(1+3=4=2^2\)
\(1+3+5=9=3^2\)
\(1+3+5+7=16=4^2\)
\(1+3+5+7+9=25=5^2\)
Постепенно начинает появляться закономерность. Попробуем записать всё в общем виде, иначе говоря, одной формулой:
\(1+3+…+(2n-1)=n^2\)
В итоге мы предполагаем, что сумма первых \(n\) нечётных чисел равна \(n^2\). То есть мы от частных рассуждений пришли к общему выводу. Но для того чтобы пользоваться формулой, в идеале мы должны её доказать. Как раз в этом нам и поможет метод математической индукции.
Теория
Введём такое обозначение: \(P(n)\) – предложение, зависящее от натурального числа \(n\).
Алгоритм метода математической индукции состоит в следующем.
Первое действие называется базой математической индукции, второе действие называется предположением.
Напомню, что мы получили такую формулу:
\(1+3+…+(2n-1)=n^2\)
Попробуем доказать её с помощью нашего метода.
1) Проверим нашу формулу для \(1\).
\(1=1\)
2) Предположим, что наша формула верна для какого-то произвольного \(k\).
\(1+3+…+(2k-1)=k^2\)
3) Докажем нашу формулу для \(k+1\).
\(1+3+…+(2k-1)+(2k+1)=(k+1)^2\)
Заменим \(1+3+…+(2k-1)=k^2\) на \(k^2\):
\(k^2+(2k+1)=(k+1)^2\)
Раскроем скобки:
\(k^2+2k+1=k^2+2k+1\)
Это верно при любом \(k\).
4) Доказали для любого \(k\). Значит, это верно и для любого \(n\).
Практика
Пример 1.
Доказать формулу
\(1^2+2^2+3^2+…+n^2= {n (n+1)(2n+1) \over 6}\)
Решение.
1) Проверяем для \(P(1)\).
\(1=1\)
2) Пусть для \(k\) – верно.
\(1^2+2^2+3^2+…+k^2= {k(k+1)(2k+1) \over 6}\)
3) Докажем для \(k + 1\).
\(1^2+2^2+3^2+…+k^2+(k+1)^2= {(k+1)(k+2)(2k+3) \over 6}\)
Заменим \(1^2+2^2+3^2+…+k^2\) на \(k(k+1)(2k+1) \over 6\):
\({k(k+1)(2k+1) \over 6}+(k+1)^2= {(k+1)(k+2)(2k+3) \over 6}\)
Раскроем скобки: \(k(k+1)(2k+1)+6(k+1)^2=(k+1)(k+2)(2k+3)\)
\(2k^3+3k^2+k+6k^2+12k+6=2k^3+3k^2+k+6k^2+12k+6\)
Это верно при любом \(k\).
4) Доказали для любого \(k\). Значит, это верно и для любого \(n\).
Пример 2.
Доказать формулу
\(1^3-2^3+3^3-4^3+…+(2n-1)^3-(2n)^3=-n^2(4n+3)\)
Решение.
1) Проверяем для \(P(1)\).
\(1=1\)
2) Пусть для \(k\) – верно.
\(1^3-2^3+3^3-4^3+…+(2k-1)^3-(2k)^3=-k^2(4k+3)\)
3) Докажем для \(k + 1\).
\(1^3-2^3+3^3-4^3+…+(2k-1)^3-(2k)^3+(2k+2)^2=-(k+1)^2(4k+7)\)
Заменим \(1^3-2^3+3^3-4^3+…+(2k-1)^3-(2k)^3\) на \(-k^2(4k+3)\).
Получим \(-k^2(4k+3)+ (2k+2)^2=-(k+1)^2(4k+7)\).
Раскроем скобки: \(-4k^3+3k^2+4k^2+8k+4=-4k^3+3k^2+4k^2+8k+4\).
Это верно при любом \(k\).
4) Доказали для любого \(k\). Значит, это верно и для любого \(n\).
Пример 3 (Ханойские башни).
Есть три стержня и \(n\) колец различного размера. Класть можно только более маленькое кольцо на более большое кольцо. Можем ли мы переместить пирамидку с одного стрежня на другой, перекладывая её кольца?
Решение.
1) Проверяем для \(P(1)\). Пирамидку, в которой только одно кольцо, переместить можно.
2) Пусть для \(k\) – верно. То есть мы можем переместить любую пирамидку с \(k\) кольцами, где \(k<n\).
3) Докажем для \(k + 1\). Нам нужно переместить пирамидку с количеством колец \(=k+1\).
Пирамидку из \(K\) колец, лежащих на самом большом \(K+1\)-м кольце, мы можем согласно предположению переместить на любой стержень. Сделаем это, переместим её на третий стержень.
После перемещения \(K\) колец переместим оставшееся \(K+1\)-е кольцо на второй стержень. Заметим, что факт того, что второй стержень не пустой, не мешает нам класть на него любые кольца, так как имеющееся на нём кольцо самое большое (любое кольцо можно положить на большее, а значит, и самое большое, по условию задачи). Снова применим известный нам по предположению алгоритм перемещения \(K\) колец и переместим их на второй стержень, стержень с лежащим внизу \(K+1\)-м кольцом.
4) Доказали для любого \(k\). Значит, это верно и для любого \(n\).
Пример 4 (неравенство Бернулли).
Доказать формулу
\((1+α)^n≥1+αn\), где \(α>-1\)
Решение.
1) Проверяем для \(P(1)\).
\(1+α≥1+α\)
2) Пусть для \(k\) – верно.
\((1+α)^k≥1+αk\)
3) Докажем для \(k + 1\).
\((1+α)^{k+1}≥1+αk+α\)
\((1+α)^α(1+α)≥1+αk+α\)
Заменим \((1+α)^k\) на \(1+αk\):
\((1+αk)(1+α)≥1+αk+α\)
Раскроем скобки:
\(1+α+αk+α^2k≥1+αk+α\)
\(α^2k\) всегда больше \(0\). Тогда это неравенство верно.
4) Доказали для любого \(k\). Значит, это верно и для любого \(n\).
Задачи для самостоятельного решения
1) Доказать формулу
\(1^3+2^3+…+n^3=({n(n+1) \over 2})^2\)
2) Доказать формулу бинома Ньютона
\((a+b)^n=a^n+C{1 \over n} a ^{n-1}b+…+C_{n} ^{n-1} ab^{n-1}+b^n\)
3) Доказать неравенство
\(2^n>n^3, \ n≥10\)
4) Доказать неравенство
\(sin^{2n}a +cos^{2n}a ≤ 1\)
5) Чему равно количество кусочков, на которые \(n\) прямых (не проходящих через одну точку) делят плоскость на части? Одна прямая – на две части, две – на четыре. А пятнадцать прямых?
