Последовательности, математическая индукция, элементы комбинаторики

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

Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 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)$  или\textstyle C_n^k и читается «биномиальный коэффициент из n по k» (или «це из n по k»):

Биномиальные коэффициенты $\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$  для $n \in \mathbb{N}$ вычисляют по формуле:

$\left( {\begin{array}{*{20}{c}}
n \\ 

\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}$.