VIDEO
Метод математической индукции
Метод математической индукции — это метод доказательства теорем об истинности некоторых утверждений -формул над целочисленной переменной: формула или схема формул сперва доказывается при некотором начальном значении этой переменной , затем ставится гипотеза -предположение об истинности формулы для произвольного целочисленного значения, а затем доказывается, что из данного предположения возможно вывести доказательство формулы над следующим значением — то есть, тем, что в ряду целых чисел следует за данным в предположении. Это доказывает истинность формулы при всех целочисленных значениях переменной, начиная с проверенного.
Обычно переменная i принимает значения из множества натуральных чисел , в таком случае для доказательства формулы для любого натурального i достаточно доказать формулу для i = 1 и доказать, что если формула верна для i = n, то она верна и для n + 1.
Своего рода инверсия метода математической индукции — это метод бесконечного спуска , которым доказывается отрицание некоего утверждения о целых числах. Обобщения метода математической индукции: трансфинитная индукция , структурная индукция и более общая над ними нётерова индукция . Обратная индукция — вычислительный принцип поиска решений задач .
Входные данные: n0 ; Sn = f(n) .
Проверяем формулу Sn = f(n) при n = n0 .0 , то формула не доказана и конец работы.
Предполагаем, что формула Sn = f(n) верна при n = k ≥ n0 .
Доказываем формулу Sn = f(n) для n = k + 1.n = f(n) верна при n = k + 1, то формула доказана для всех n = k ≥ n0 , иначе формула не доказана. Доказать формулу
∑
i
=
1
n
i
2
=
n
(
n
+
1
)
(
2
n
+
1
)
6
{\displaystyle \sum \limits _{i=1}^{n}i^{2}={\frac {n(n+1)(2n+1)}{6}}}
Введем обозначения:
S
n
=
∑
i
=
1
n
i
2
=
1
2
+
2
2
+
…
+
n
2
;
{\displaystyle S_{n}=\sum \limits _{i=1}^{n}i^{2}=1^{2}+2^{2}+\ldots +n^{2};}
f
(
n
)
=
n
(
n
+
1
)
(
2
n
+
1
)
6
{\displaystyle f(n)={\frac {n(n+1)(2n+1)}{6}}}
Доказательство.
1. Проверяем формулу
S
n
=
f
(
n
)
{\displaystyle S_{n}=f(n)}
n
=
1
{\displaystyle n=1}
{
n
=
1
S
n
=
∑
i
=
1
n
i
2
f
(
n
)
=
n
(
n
+
1
)
(
2
n
+
1
)
6
⇒
{
S
1
=
∑
i
=
1
1
i
2
=
1
2
=
1
f
(
1
)
=
1
⋅
(
1
+
1
)
⋅
(
2
⋅
1
+
1
)
6
=
1
⋅
2
⋅
3
6
=
1
⇒
{\displaystyle {\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 }
S
1
=
f
(
1
)
⇒
{
n
=
1
S
n
=
f
(
n
)
{\displaystyle S_{1}=f(1)\Rightarrow {\begin{cases}n=1\\S_{n}=f(n)\end{cases}}}
n
=
1
{\displaystyle n=1}
2.Предполагаем, что формула
S
n
=
f
(
n
)
{\displaystyle S_{n}=f(n)}
n
=
k
{\displaystyle n=k}
∑
i
=
1
k
i
2
=
k
(
k
+
1
)
(
2
k
+
1
)
6
{\displaystyle \sum \limits _{i=1}^{k}i^{2}={\frac {k(k+1)(2k+1)}{6}}}
3.Доказываем формулу
S
n
=
f
(
n
)
{\displaystyle S_{n}=f(n)}
n
=
k
+
1
{\displaystyle n=k+1}
S
k
+
1
=
∑
i
=
1
k
+
1
i
2
=
∑
i
=
1
k
i
2
+
(
k
+
1
)
2
=
k
(
k
+
1
)
(
2
k
+
1
)
6
+
(
k
+
1
)
2
=
{\displaystyle 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}=}
=
k
(
k
+
1
)
(
2
k
+
1
)
+
6
(
k
+
1
)
2
6
=
(
k
+
1
)
[
k
(
2
k
+
1
)
+
6
(
k
+
1
)
]
6
=
{\displaystyle ={\frac {k(k+1)(2k+1)+6(k+1)^{2}}{6}}={\frac {(k+1)\left[k(2k+1)+6(k+1)\right]}{6}}=}
=
(
k
+
1
)
[
(
2
k
2
+
k
)
+
(
6
k
+
6
)
]
6
=
(
k
+
1
)
(
2
k
2
+
7
k
+
6
)
6
=
{\displaystyle ={\frac {(k+1)\left[(2k^{2}+k)+(6k+6)\right]}{6}}={\frac {(k+1)(2k^{2}+7k+6)}{6}}=}
=
(
k
+
1
)
(
k
+
2
)
(
2
k
+
3
)
6
;
{\displaystyle ={\frac {(k+1)(k+2)(2k+3)}{6}};}
f
(
k
+
1
)
=
(
k
+
1
)
(
(
k
+
1
)
+
1
)
(
2
(
k
+
1
)
+
1
)
6
=
(
k
+
1
)
(
k
+
2
)
(
2
k
+
3
)
6
⇒
{\displaystyle 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 }
⇒
S
k
+
1
=
f
(
k
+
1
)
⇒
{
n
=
k
+
1
S
n
=
f
(
n
)
{\displaystyle \Rightarrow S_{k+1}=f(k+1)\Rightarrow {\begin{cases}n=k+1\\S_{n}=f(n)\end{cases}}}
n
=
k
+
1
{\displaystyle n=k+1}
Формула доказана, ч.т.д.
Доказать формулу
∑
i
=
1
n
i
3
=
n
2
(
n
+
1
)
2
4
{\displaystyle \sum \limits _{i=1}^{n}i^{3}={\frac {n^{2}(n+1)^{2}}{4}}}
Введем обозначения:
S
n
=
∑
i
=
1
n
i
3
=
1
3
+
2
3
+
…
+
n
3
;
{\displaystyle S_{n}=\sum \limits _{i=1}^{n}i^{3}=1^{3}+2^{3}+\ldots +n^{3};}
f
(
n
)
=
n
2
(
n
+
1
)
2
4
{\displaystyle f(n)={\frac {n^{2}(n+1)^{2}}{4}}}
Доказательство.
1. Проверяем формулу
S
n
=
f
(
n
)
{\displaystyle S_{n}=f(n)}
n
=
1
{\displaystyle n=1}
{
n
=
1
S
n
=
∑
i
=
1
n
i
3
f
(
n
)
=
n
2
(
n
+
1
)
2
4
⇒
{
S
1
=
∑
i
=
1
1
i
3
=
1
3
=
1
f
(
1
)
=
1
2
⋅
(
1
+
1
)
2
4
=
1
⋅
2
2
4
=
1
⇒
{\displaystyle {\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 }
S
1
=
f
(
1
)
⇒
{
n
=
1
S
n
=
f
(
n
)
{\displaystyle S_{1}=f(1)\Rightarrow {\begin{cases}n=1\\S_{n}=f(n)\end{cases}}}
n
=
1
{\displaystyle n=1}
2.Предполагаем, что формула
S
n
=
f
(
n
)
{\displaystyle S_{n}=f(n)}
n
=
k
{\displaystyle n=k}
∑
i
=
1
k
i
3
=
k
2
(
k
+
1
)
2
4
{\displaystyle \sum \limits _{i=1}^{k}i^{3}={\frac {k^{2}(k+1)^{2}}{4}}}
3.Доказываем формулу
S
n
=
f
(
n
)
{\displaystyle S_{n}=f(n)}
n
=
k
+
1
{\displaystyle n=k+1}
S
k
+
1
=
∑
i
=
1
k
+
1
i
3
=
∑
i
=
1
k
i
3
+
(
k
+
1
)
3
=
k
2
(
k
+
1
)
2
4
+
(
k
+
1
)
3
=
k
2
(
k
+
1
)
2
+
4
(
k
+
1
)
3
4
=
{\displaystyle 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}}=}
=
(
k
+
1
)
2
[
k
2
+
4
(
k
+
1
)
]
4
=
(
k
+
1
)
2
(
k
2
+
4
k
+
4
)
4
=
(
k
+
1
)
2
(
k
+
2
)
2
4
;
{\displaystyle ={\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}};}
f
(
k
+
1
)
=
(
k
+
1
)
2
[
(
k
+
1
)
+
1
]
2
4
=
(
k
+
1
)
2
(
k
+
2
)
2
4
⇒
{\displaystyle f(k+1)={\frac {(k+1)^{2}\left[(k+1)+1\right]^{2}}{4}}={\frac {(k+1)^{2}(k+2)^{2}}{4}}\Rightarrow }
⇒
S
k
+
1
=
f
(
k
+
1
)
⇒
{
n
=
k
+
1
S
n
=
f
(
n
)
{\displaystyle \Rightarrow S_{k+1}=f(k+1)\Rightarrow {\begin{cases}n=k+1\\S_{n}=f(n)\end{cases}}}
n
=
k
+
1
{\displaystyle n=k+1}
Формула доказана, ч.т.д.
Некорректное применение метода математической индукции может вести к логическим парадоксам — см., например, Доказательство одноцветности всех лошадей (автор — Дьёрдь Пойа ). См. также Парадокс кучи .
Другие алгоритмы [ править ] 
![{\displaystyle ={\frac {k(k+1)(2k+1)+6(k+1)^{2}}{6}}={\frac {(k+1)\left[k(2k+1)+6(k+1)\right]}{6}}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f20c6f886a04ca2631b436777afdeff1aef0dbc5)
![{\displaystyle ={\frac {(k+1)\left[(2k^{2}+k)+(6k+6)\right]}{6}}={\frac {(k+1)(2k^{2}+7k+6)}{6}}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44b773450b6082393c048177b7481a0c82198dc9)
![{\displaystyle ={\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}};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2588dc24c70299203b1ef0515cd832aa5e0a567b)
![{\displaystyle f(k+1)={\frac {(k+1)^{2}\left[(k+1)+1\right]^{2}}{4}}={\frac {(k+1)^{2}(k+2)^{2}}{4}}\Rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/88f5f2f8ad62f2a5e77942adf7d73dfd67a1faeb)