Teorema Binomial dan Identitas Kombinatorial

Hallo guys pada kesempatan ini kita akan membahas tentang teorema binomial dan identitas kombinatorial termasuk juga identitas Vandermonde. Oke langsung saja ke pembahasannya.

Teorema Binomial

Untuk setiap $n\geq 0$,

$(x+y)^n$ $=\binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+\cdots +\binom{n}{n-1}xy^{n-1}+\binom{n}{n}y^n$ $=\sum_{r=0}^n \binom{n}{r}x^{n-r}y^r$

Bukti 1: Dengan menggunakan induksi matematika.

Untuk $n=0$, $(x+y)^0=1=\binom{0}{0}x^0y^0$

Assumsikan bahwa benar untuk $n=k$ berlaku untuk beberapa $k\geq 0$

$(x+y)^k=\sum_{r=0}^k \binom{k}{r}x^{k-r}y^r$

Perhatikan untuk $n=k+1$ kita punya

$(x+y)^{k+1}=(x+y)(x+y)^k$ $=(x+y)\sum_{r=0}^k \binom{k}{r}x^{k-r}y^r$ $=\sum_{r=0}^k \binom{k}{r}x^{k+1-r}y^r+\sum_{r=0}^k \binom{k}{r}x^{k-r}y^{r+1}$ $=\binom{k}{0}x^{k+1}+\binom{k}{1}x^{k}y+\cdots +\binom{k}{k-1}x^2y^{k-1}+\binom{k}{k}xy^k$ $+\binom{k}{0}x^ky+\binom{k}{1}x^{k-1}y^2+\cdots +\binom{k}{k-1}xy^k+\binom{k}{k}y^{k+1}$ $=\binom{k+1}{0}x^{k+1}+\binom{k+1}{1}x^{k}y+\cdots +\binom{k+1}{k}xy^{k}+\binom{k+1}{k+1}y^{k+1}$

(Terbukti)

Bukti 2: Dengan bukti kombinatorial.

Cukup ditunjukkan bahwa koefisien $x^{n-r}y^r$ dari ekspresi $(x+y)^n$ adalah $\binom{n}{r}$

Pandang bahwa

$(x+y)^n=(x+y)(x+y)\cdots (x+y)$

Koefisien suku $x^{n-r}y^r$ dari ekspansi perkalian tersebut sama halnya dengan memilih $r$ faktor $(x+y)$ yang tidak lain adalah $\binom{n}{r}$

(Terbukti)

Identitas Kombinatorial

Berikut beberapa contoh identitas kombinatorial.

Tunjukan bahwa untuk setiap bilangan bulat $n\geq 0$,

$\begin{align*}&\sum_{r=0}^n\binom{n}{r}\\ &=\binom{n}{0}+\binom{n}{1}+\cdots +\binom{n}{n}\\ &=2^n\end{align*}$

Bukti : Menurut teorema binomial sebelumnya

$(x+y)^n=\binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+\cdots +\binom{n}{n-1}xy^{n-1}+\binom{n}{n}y^n$

Substitusi $x=y=1$ diperoleh

$2^n=\binom{n}{0}+\binom{n}{1}+\cdots +\binom{n}{n-1}+\binom{n}{n}$

(Terbukti)

Tunjukan bahwa untuk setiap bilangan bulat $n\geq 1$,

i)

$\begin{align*}&\sum_{r=0}^n(-1)^r\binom{n}{r}\\ &=\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\cdots +(-1)^n\binom{n}{n}\\ &=0\end{align*}$

Bukti : Menurut teorema binomial sebelumnya

$(x+y)^n=\binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+\cdots +\binom{n}{n-1}xy^{n-1}+\binom{n}{n}y^n$

Substitusi $x=1$ dan $y=-1$ diperoleh

$0=\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\cdots +(-1)^n\binom{n}{n}$

(Terbukti)

ii)

$\begin{align*}&\binom{n}{0}+\binom{n}{2}+\cdots +\binom{n}{2k}+\cdots\\ &=\binom{n}{1}+\binom{n}{3}+\cdots +\binom{n}{2k+1}+\cdots\\ &=2^{n-1}\end{align*}$

Bukti : Sekarang kita punya dua identitas kombinatorial

$\begin{align*}\binom{n}{0}+\binom{n}{1}+\cdots +\binom{n}{n}=2^n\end{align*}$

dan

$\begin{align*}\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\cdots +(-1)^n\binom{n}{n}=0\end{align*}$

Kita jumlahkan kedua persamaan kemudian dibagi 2. Disisi lain kita kurangkan kedua persamaan kemudian dibagi 2. Maka kita sudah membuktikan yang kita minta.

Tunjukan bahwa untuk setiap bilangan asli $n$,

$\begin{align*}&\sum_{r=0}^nr\binom{n}{r}\\ &=\binom{n}{1}+2\binom{n}{2}+\cdots +n\binom{n}{n}\\ &=n2^{n-1}\end{align*}$

Bukti : Menurut teorema binomial sebelumnya

$(x+y)^n=\binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+\cdots +\binom{n}{n-1}xy^{n-1}+\binom{n}{n}y^n$

Substitusi $x=1$ kita peroleh

Menurut teorema binomial sebelumnya

$(1+y)^n=\binom{n}{0}+\binom{n}{1}y+\cdots +\binom{n}{n-1}y^{n-1}+\binom{n}{n}y^n$

Turunkan kedua ruas terhadap $y$ diperoleh

$n(1+y)^{n-1}=\binom{n}{1}+\cdots +(n-1)\binom{n}{n-1}y^{n-2}+n\binom{n}{n}y^{n-1}$

Substitusi $y=1$

$n2^{n-1}=\binom{n}{1}+\cdots +(n-1)\binom{n}{n-1}+n\binom{n}{n}$

(Terbukti)

(Identitas Vandermonde) Untuk setiap bilangan asli $m,n,r$,

$\begin{align*}&\sum_{i=0}^r\binom{m}{i}\binom{n}{r-i}\\ &=\binom{m}{0}\binom{n}{r}+\binom{m}{1}\binom{n}{r-1}+\cdots +\binom{m}{r}\binom{n}{0}\\ &=\binom{m+n}{r}\end{align*}$