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

Ако предикат (реченица) $P\left( n \right)$, чија променљива $n$   узима вредности из скупа природних бројева, задовољава следећа два услова:

1. $P\left( 1 \right)$ је тачан исказ,
2. Из предпоставке да је $P\left( k \right)$ тачан исказ за неки природан број $k$, следи да је $P\left( {k + 1} \right)$ тачан исказ, тј. $P\left( k \right) \Rightarrow P\left( {k + 1} \right)$ је тачан исказ, онда је $P\left( n \right)$ тачан исказ за сваки природан број $n$

Ово тврђење се у математици користи као метод за доказивање разних теорема. При том се доказ састоји из два корака. У првом, који се назива база индукције, доказује се тачност исказа $P\left( 1 \right)$., а у другом, који се назива индуктивни корак, доказује се тачност импликације $P\left( k \right) \Rightarrow P\left( {k + 1} \right)$. Исказ $P\left( k \right)$ се назива индуктивна хипотеза (предпоставка). Ако $P\left( n \right)$ важи за свако $n \geqslant {n_0} \in \mathbb{N}$, тада за базу индукције имамо, уместо $P\left( 1 \right)$ , исказ $P\left( {{n_0}} \right)$.

Биномни коефицијенти

Факторијал

Факторијал $n!$ произвољног целог броја $n \geqslant 0$ је дефинисан са

$0! = 1,\quad n! = \left( {n - 1} \right)! \cdot n,\quad n = \mathbb{N}$.

Следи

$n! = 1 \cdot 2 \cdot  \cdot  \cdot \left( {n - 1} \right) \cdot n,\quad n \in \mathbb{N}$

Биномни коефицијет $\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$ се дефинише за  $n \in \mathbb{R}$

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

Биномна формула

Нека је $a,b \in \mathbb{R}$ и $n \in \mathbb{N}$. Тада је

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