Binomni poučak

☰ 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 -tog reda je svaka bijekcija s $[1,n]_{\mathbb{N}}$ u $[1,n]_{\mathbb{N}}$ . Kombinacija -tog reda i -tog razreda je svaki

-člani podskup $\{i_1,i_2,\ldots,i_k\}\subseteq [1,n]_{\mathbb{N}}$ . Pri tome je dopušten i slučaj

U teoremu 2.7 je dokazano da skup svih različitih permutacija -tog reda ima elemenata ( 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

-tog reda i

-tog razreda

jednak je binomnom koeficijentu

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

Dokaz.

Svaku permutaciju

-tog reda možemo dobiti u tri koraka:

1.: odaberemo jedan -člani podskup od $[1,n]_{\mathbb{N}}$ , što možemo učiniti na načina;
2.: odaberemo jednu permutaciju tog podskupa, što možemo učiniti na načina;
3.: odaberemo jednu permutaciju preostalog -članog podskupa, što možemo učiniti na načina.

Ukupan broj permutacija

-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)

-tom retku Pascalovog trokuta nalaze se binomni koeficijenti

-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 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 skup svih prirodnih brojeva za koje formula vrijedi. Dokažimo da je $M=\mathbb{N}$ . Za 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

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