Доказательство методом математической индукции
| English | Русский |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | положительное целое число |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | математическая индукция |
| base case/beɪs keɪs/ | базовым случаем |
| inductive step/ɪnˈdʌktɪv step/ | шаг индукции |
| conjecture/kənˈdʒektʃə/ | гипотеза |
| divisible/dɪˈvɪzɪbl/ | делимый |
Доказательство методом «домино»
- Как доказать, что утверждение верно для каждого положительного целого числа — бесконечного множества случаев?
- Математическая индукция работает как домино: толкнуть первую косточку (базовый случай) и показать, что каждая последующая толкает следующую (индукционный переход). Если оба условия выполнены, все падут.
Маршрут доказательства методом математической индукции
Представьте индукцию как первый падающий домино plus правило, толкающее каждый следующий случай.
Два шага индукции
- Математическая индукция доказывает результат для каждого положительного целого числа $n$ в два этапа:
- Базовый случай: покажите, что это верно для $n = 1$.
- Индукционный переход: предположите, что это верно для $n = k$, затем докажите это для $n = k + 1$.
Разобраный пример. Доказать $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. Базовый случай ($n=1$): Левая часть $= 1$, Правая часть $= \dfrac{1(2)}{2} = 1$. ✓ Индукционный переход: Предположим, верно для $n = k$. Для $n = k+1$: $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$. ✓
Доказательство по индукции работает как цепочка падающих косточек домино
Два шага доказательства методом математической индукции — это базовый случай и:
Индукция требует базового случая плюс индукционного шага от k к k+1.
Базовый случай обычно показывает, что результат верен для:
Базовый случай проверяет наименьшее значение, обычно n = 1.
Если верны и базовый случай, и индукционный шаг, то результат справедлив для всех положительных целых чисел n.
Именно это гарантирует принцип математической индукции.
Почему оба шага обязательны
- Базовый случай запускает цепь. Без него можно «доказать» ложные утверждения.
- Индукционный переход расширяет его. Без него вы доказали только один случай.
Оба шага обязательны. Доказательство только с индукционным переходом похоже на ряд домино, который никто не толкает — он никогда не начнется падать. Доказательство только с базовым случаем похоже на то, чтобы толкнуть одну косточку — упадет только одна.
Результат можно доказать методом индукции, используя только индукционный шаг, без базового случая.
Оба шага необходимы. Без базового случая цепочка никогда не начнется.
Гипотеза, затем доказательство
- Часто вы делаете гипотезу (разумное предположение) на основе нескольких случаев, а затем подтверждаете её доказательством по индукции.
- Пример: $1 + 3 + 5 + 7 = 16 = 4^2$. Гипотеза: сумма первых $n$ нечетных чисел равна $n^2$.
Используя индукцию, сумма 1 + 2 + ... + n = n(n+1)/2. Для n = 10 найдите сумму.
10(11)/2 = 55.
Индукция для делимости
- Доказать, что $3^n - 1$ делится на $2$ для всех положительных целых $n$.
- Базовый случай ($n=1$): $3^1 - 1 = 2$, делится на $2$. ✓
- Индукционный переход: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. Поскольку $3^k - 1$ делится на $2$ (по предположению), то и всё выражение делится. ✓
В математике гипотеза — это:
Гипотеза — это недоказанное утверждение, основанное на доказательствах evidence — затем вы пытаетесь его доказать (часто методом индукции).
Вы поняли
- индукция = базовый случай ($n=1$) + индукционный переход ($n=k \Rightarrow n=k+1$)
- оба шага вместе доказывают это для всех положительных целых чисел
- часто гипотеза из случаев, затем доказательство по индукции