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

Материал из Циклопедии
Перейти к: навигация, поиск
Метод математической индукции

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

Обычно переменная i принимает значения из множества натуральных чисел, в таком случае для доказательства формулы для любого натурального i достаточно доказать формулу для i = 1 и доказать, что если формула верна для i = n, то она верна и для n + 1.

Содержание

[править] Алгоритм

Входные данные: n0; Sn = f(n).

  1. Проверяем формулу Sn = f(n) при n = n0.
    Если формула не верна при n = n0, то формула не доказана и конец работы.
  2. Предполагаем, что формула Sn = f(n) верна при n = k ≥ n0.
  3. Доказываем формулу Sn = f(n) для n = k + 1.
    Если формула Sn = f(n) верна при n = k + 1, то формула доказана для всех n = k ≥ n0, иначе формула не доказана.

[править] Примеры

[править] Пример 1

Доказать формулу [math]\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}[/math].

Введем обозначения:

[math]S_n = \sum\limits_{i=1}^n i^2 = 1^2+ 2^2 + \ldots + n^2;[/math].
[math]f(n) = \frac{n(n+1)(2n+1)}{6}[/math].

Доказательство.

1. Проверяем формулу [math]S_n=f(n)[/math] при [math]n=1[/math].

[math]\begin{cases}n=1 \\ S_n=\sum\limits_{i=1}^n i^2 \\ f(n) = \frac{n(n+1)(2n+1)}{6} \end{cases} \Rightarrow \begin{cases}S_1=\sum\limits_{i=1}^1 i^2 = 1^2 = 1 \\ f(1) = \frac{1\cdot(1+1)\cdot(2\cdot 1+1)}{6} = \frac{1\cdot 2 \cdot 3}{6} = 1\end{cases} \Rightarrow[/math]
[math]S_1=f(1) \Rightarrow \begin{cases}n=1 \\ S_n=f(n)\end{cases}[/math], то есть формула верна при [math]n=1[/math]

2.Предполагаем, что формула [math]S_n=f(n)[/math] верна при [math]n=k[/math], то есть

[math]\sum\limits_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}[/math].

3.Доказываем формулу [math]S_n=f(n)[/math] для [math]n=k+1[/math].

[math]S_{k+1}=\sum\limits_{i=1}^{k+1} i^2 =\sum\limits_{i=1}^k i^2 + (k+1)^2 =\frac{k(k+1)(2k+1)}{6} + (k+1)^2 =[/math]
[math]=\frac{k(k+1)(2k+1)+6(k+1)^2}{6}=\frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6}=[/math]
[math]=\frac{(k+1)\left[(2k^2+k)+(6k+6)\right]}{6}=\frac{(k+1)(2k^2+7k+6)}{6}=[/math]
[math]=\frac{(k+1)(k+2)(2k+3)}{6};[/math]
[math]f(k+1)=\frac{\left(k+1\right)\left((k+1)+1\right)\left(2(k+1)+1\right)}{6}=\frac{(k+1)(k+2)(2k+3)}{6} \Rightarrow[/math]
[math]\Rightarrow S_{k+1}=f(k+1) \Rightarrow \begin{cases}n=k+1 \\ S_n=f(n)\end{cases}[/math], то есть формула верна при [math]n=k+1[/math].

Формула доказана, ч.т.д.

[править] Пример 2

Доказать формулу [math]\sum\limits_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}[/math].

Введем обозначения:

[math]S_n = \sum\limits_{i=1}^n i^3 = 1^3+ 2^3 + \ldots + n^3;[/math].
[math]f(n) = \frac{n^2(n+1)^2}{4}[/math].

Доказательство.

1. Проверяем формулу [math]S_n=f(n)[/math] при [math]n=1[/math].

[math]\begin{cases}n=1 \\ S_n=\sum\limits_{i=1}^n i^3 \\ f(n) = \frac{n^2(n+1)^2}{4} \end{cases} \Rightarrow \begin{cases}S_1=\sum\limits_{i=1}^1 i^3 = 1^3 = 1 \\ f(1) = \frac{1^2\cdot(1+1)^2}{4} = \frac{1\cdot 2^2}{4} = 1\end{cases} \Rightarrow[/math]
[math]S_1=f(1) \Rightarrow \begin{cases}n=1 \\ S_n=f(n)\end{cases}[/math], то есть формула верна при [math]n=1[/math]

2.Предполагаем, что формула [math]S_n=f(n)[/math] верна при [math]n=k[/math], то есть

[math]\sum\limits_{i=1}^k i^3 = \frac{k^2(k+1)^2}{4}[/math].

3.Доказываем формулу [math]S_n=f(n)[/math] для [math]n=k+1[/math].

[math]S_{k+1}=\sum\limits_{i=1}^{k+1} i^3 =\sum\limits_{i=1}^k i^3 + (k+1)^3 =\frac{k^2(k+1)^2}{4} + (k+1)^3 = \frac{k^2(k+1)^2+4(k+1)^3}{4} =[/math]
[math]=\frac{(k+1)^2\left[k^2+4(k+1)\right]}{4}=\frac{(k+1)^2(k^2+4k+4)}{4}=\frac{(k+1)^2(k+2)^2}{4};[/math]
[math]f(k+1)=\frac{(k+1)^2\left[(k+1)+1\right]^2}{4}=\frac{(k+1)^2(k+2)^2}{4} \Rightarrow[/math]
[math]\Rightarrow S_{k+1}=f(k+1) \Rightarrow \begin{cases}n=k+1 \\ S_n=f(n)\end{cases}[/math], то есть формула верна при [math]n=k+1[/math].

Формула доказана, ч.т.д.

[править] Разное

Некорректное применение метода математической индукции может вести к логическим парадоксам — см., например, Доказательство одноцветности всех лошадей (автор — Дьёрдь Пойа). См. также Парадокс кучи.

[править] Другие алгоритмы

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты