Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1.
Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: $P\left( n \right)$.
Допустим, что
- Установлено, что $P\left( 1 \right)$ верно. (Это утверждение называется базой индукции.)
- И мы умеем доказывать для любого $k$, что из верности утверждени $P\left( k \right)$, следует верность $P\left( {k + 1} \right)$. (Это утверждение называется индукционным переходом.)
Тогда все утверждения нашей последовательности верны.
Факториал
Факториал $n!$ числа $n$ — это произведение всех натуральных чисел от 1 до $n$ включительно:
$n! = 1 \cdot 2 \cdot \cdot \cdot \left( {n — 1} \right) \cdot n,\quad n \in \mathbb{N}$.
$0! = 1,\quad n! = \left( {n — 1} \right)! \cdot n,\quad n = \mathbb{N}$.
Биноминальные коэффициенты
Биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона ${\left( {1 + x} \right)^n}$ по степеням x. Коэффициент при ${\left( { x} \right)^k}$ обозначается $\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$ или
и читается «биномиальный коэффициент из n по k» (или «це из n по k»):
Биномиальные коэффициенты $\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$ для $n \in \mathbb{N}$ вычисляют по формуле:
$\left( {\begin{array}{*{20}{c}}
n \\
k
\end{array}} \right) = \left\{ {\begin{array}{*{20}{c}}
{1,} \\
{\frac{{n(n — 1)(n — 2)(n — 3) \cdot \cdot \cdot (n — k + 1)}}{{k!}}}
\end{array}{\text{, }}\begin{array}{*{20}{c}}
{k = 0,} \\
{k \in \mathbb{N}.}
\end{array}} \right.$
Пусть $k \leqslant n$ и $k,n \in \mathbb{N}$. Тогда
$\left( {\begin{array}{*{20}{c}}
n \\ k
\end{array}} \right) = \frac{{n!}}{{k!\left( {n — k} \right)!}};{\text{ }}\left( {\begin{array}{*{20}{c}}
n \\ k
\end{array}} \right) = \left( {\begin{array}{*{20}{c}}
n \\ {n — k}
\end{array}} \right);{\text{ }}\left( {\begin{array}{*{20}{c}}
{n — 1} \\ k
\end{array}} \right) + \left( {\begin{array}{*{20}{c}}
{n — 1} \\ {k — 1}
\end{array}} \right) = \left( {\begin{array}{*{20}{c}}
n \\ k
\end{array}} \right).$
Бином Ньютона — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид:
${\left( {a + b} \right)^n} = \left( {\begin{array}{*{20}{c}} n \\ 0
\end{array}} \right){a^n} + \left( {\begin{array}{*{20}{c}} n \\ 1
\end{array}} \right){a^{n — 1}}b + \left( {\begin{array}{*{20}{c}} n \\ 2
\end{array}} \right){a^{n — 2}}{b^2} + \cdot \cdot \cdot + \left( {\begin{array}{*{20}{c}}
n \\ {n — 1} \end{array}} \right)a{b^{n — 1}} + \left( {\begin{array}{*{20}{c}}
n \\ n \end{array}} \right){b^n},$
или короче
${\left( {a + b} \right)^n} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right){a^{n — k}}{b^k}.} $,
где $a,b \in \mathbb{R}$ и $n \in \mathbb{N}$.
