×   HOME JAVA NETPLOT OCTAVE Traži ...
  matematika1
Uređaj na skupu prirodnih     Prirodni brojevi     Cijeli brojevi


Binomni poučak

U ovom poglavlju definirat ćemo permutaciju i kombinaciju, opisati Pascalov trokut i dokazati binomni poučak i neke njegove posljedice.

Definicija 1.16   Permutacija $ n$ -tog reda je svaka bijekcija s $ [1,n]_{\mathbb{N}}$ u $ [1,n]_{\mathbb{N}}$ . Kombinacija $ n$ -tog reda i $ k$ -tog razreda je svaki $ k$ -člani podskup $ \{i_1,i_2,\ldots,i_k\}\subseteq [1,n]_{\mathbb{N}}$ . Pri tome je dopušten i slučaj $ k=0$ .

U teoremu 2.7 je dokazano da skup svih različitih permutacija $ n$ -tog reda ima $ n!$ elemenata ($ n$ faktorijela). Faktorijele su definirane rekurzivno s

$\displaystyle %
(n+1)!=n!(n+1)\quad \textrm{uz dogovor}\quad 0!=1,
$

ili kao funkcija $ f:\mathbb{N}\to \mathbb{N}$ zadana s

$\displaystyle %
f(1)=1,\quad f(n+1)=f(n)\cdot (n+1).
$

Teorem 1.4   Broj različitih kombinacija $ n$ -tog reda i $ k$ -tog razreda $ K_n^k$ jednak je binomnom koeficijentu

$\displaystyle %
\binom{n}{k}=\frac{n!}{k!(n-k)!}.
$

Dokaz.

Svaku permutaciju $ n$ -tog reda možemo dobiti u tri koraka:
1.
odaberemo jedan $ k$ -člani podskup od $ [1,n]_{\mathbb{N}}$ , što možemo učiniti na $ K_n^k$ načina;
2.
odaberemo jednu permutaciju tog podskupa, što možemo učiniti na $ k!$ načina;
3.
odaberemo jednu permutaciju preostalog $ (n-k)$ -članog podskupa, što možemo učiniti na $ (n-k)!$ načina.
Ukupan broj permutacija $ n$ -tog reda stoga je jednak

$\displaystyle %
n!=K_n^k\cdot k!\cdot (n-k)!
$

pa je teorem dokazan.     
Q.E.D.

Teorem 1.5   Vrijedi

$\displaystyle \binom{n}{k}$ $\displaystyle =\binom{n}{n-k},\qquad \forall k,n\in\mathbb{N}\cup \{0\}, \quad k\leq n,$    
$\displaystyle \binom{n}{k}+\binom{n}{k+1}$ $\displaystyle =\binom{n+1}{k+1},\qquad \forall k,n\in\mathbb{N}\cup \{0\},\quad k <n.$    

Zadatak 1.3   Dokažite teorem 1.5.

Druga tvrdnja teorema 1.5 daje nam poznati Pascalov trokut:

\begin{displaymath}\begin{array}{ccccccccccccc} & & & & & & 1 & & & & & & \\ \\ ...
...& 20& &15& & 6& &1\\ \\ \vdots &&&&&& &&&&&& \vdots \end{array}\end{displaymath} (1.1)

U $ n$ -tom retku Pascalovog trokuta nalaze se binomni koeficijenti $ n$ -tog reda, $ n=0,1,2,3,\ldots$ , i to poredani po razredu $ k=0,1,2\cdots,n$ . Vidimo da je svaki element, osim rubnih, zbroj dvaju elemenata koji se nalaze s lijeve i desne strane u retku iznad.

Teorem 1.6   [Binomni poučak] Za svaki $ n\in \mathbb{N}$ vrijedi

$\displaystyle (a+b)^n=\sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}.$ (1.2)

Na primjer, formula (1.2) i Pascalov trokut (1.1) za $ n=4$ daju

$\displaystyle (a+b)^4$ $\displaystyle =\binom{4}{0}a^0b^4+\binom{4}{1}a^1b^3+\binom{4}{2}a^2b^2+ \binom{4}{3}a^3b^1+\binom{4}{4}a^4b^0$    
  $\displaystyle =b^4+4ab^3+6a^2b^2+4a^3b+a^4.$    

Binomni poučak dokazat ćemo za prirodne brojeve, no on vrijedi i za racionalne, realne i kompleksne brojeve.

Dokaz.

Teorem ćemo dokazati pomoću principa matematičke indukcije P4 iz definicije 1.13. Tehnika dokazivanja slična je onoj iz Primjera 1.3.

Neka je $ M$ skup svih prirodnih brojeva za koje formula vrijedi. Dokažimo da je $ M=\mathbb{N}$ . Za $ n=1$ formula vrijedi jer je

$\displaystyle %
(a+b)^1=\binom{1}{0}a^0b^1+\binom{1}{1}a^1b^0.
$

Dakle, $ 1\in M$ pa je ispunjena baza indukcije, odnosno uvjet i) aksioma P4. Pokažimo da je ispunjen i korak indukcije, odnosno uvjet ii) aksioma P4. Ako je $ n\in M$ , odnosno ako formula vrijedi za $ n$ , tada je

$\displaystyle (a+b)^{n+1}$ $\displaystyle =\left[\sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}\right] (a+b)$    
  $\displaystyle =\sum_{k=0}^{n} \binom{n}{k} a^{k+1} b^{n-k}+ \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k+1}$    
  $\displaystyle =\sum_{k=1}^{n+1} \binom{n}{k-1} a^{k} b^{n-(k-1)}+ \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k+1}$    
  $\displaystyle =\binom{n}{n}a^{n+1}b^0+ \sum_{k=1}^{n} \binom{n}{k-1} a^{k} b^{n-k+1}+ \sum_{k=1}^{n} \binom{n}{k} a^k b^{n-k+1}$    
  $\displaystyle \quad +\binom{n}{0}a^0b^{n+1}$    
  $\displaystyle =\binom{n}{n}a^{n+1}b^0+ \sum_{k=1}^{n}\left[\binom{n}{k-1}+\binom{n}{k}\right] a^k b^{n-k+1}+ \binom{n}{0}a^0b^{n+1}$    
  $\displaystyle =\binom{n+1}{n+1}a^{n+1}b^0+ \sum_{k=1}^{n} \binom{n+1}{k} a^k b^{n+1-k}+ \binom{n+1}{0}a^0b^{n+1}$    
  $\displaystyle =\sum_{k=0}^{n+1} \binom{n+1}{k} a^k b^{n+1-k}.$    

U predzadnjoj jednakosti koristili smo Pascalov trokut (1.1). Dakle, $ n+1\in M$ pa aksiom P4 povlači $ M=\mathbb{N}$ i teorem je dokazan.     
Q.E.D.

Korolar 1.1   Za svaki $ n\in \mathbb{N}$ vrijedi

$\displaystyle %
(a-b)^n=(a+(-1)b)^n=\sum_{k=0}^{n} \binom{n}{k} (-1)^{n-k}a^k b^{n-k}
$

i

$\displaystyle %
2^n=\sum_{k=0}^{n} \binom{n}{k},
$

odnosno zbroj elemenata u $ n$ -tom retku Pascalovog trokuta (1.1) jednak je $ 2^n$ .


Uređaj na skupu prirodnih     Prirodni brojevi     Cijeli brojevi