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

Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1.

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами:  $P\left( n \right)$.

Допустим, что

1. Установлено, что $P\left( 1 \right)$ верно. (Это утверждение называется базой индукции.)
2.  И мы умеем доказывать для любого  $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}$.