CSCE 222 Lecture 24

« previous | Monday, April 4, 2011 | next »

Generating Functions (cont'd)

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=\left\{ \underbrace{1,\ldots,1}_{n+1},0,0,\ldots \right\}} , the generating function is truncated form of a geometric series:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^n x^k = 1+x+\dots+x^n = \frac{1-x^{n+1}}{1-x}}

Now use what we learned in calculus:

$G(x)$	$a_{k}$
$(1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,x^{k}=1+{\binom {n}{1}}\,x+{\binom {n}{2}}\,x^{2}+\dots +x^{n}$	${\binom {n}{k}}$
$(1+ax)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,a^{k}x^{k}=1+{\binom {n}{1}}\,ax+{\binom {n}{2}}\,a^{2}x^{2}+\dots +a^{n}x^{n}$	${\binom {n}{k}}\,a^{k}$
$\left(1+x^{r}\right)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,x^{rk}=1+{\binom {n}{1}}\,x^{r}+{\binom {n}{2}}\,x^{2r}+\dots +x^{rn}$	${\binom {n}{\frac {k}{r}}}$ if $r$ divides $k$; 0 otherwise.
${\frac {1-x^{n+1}}{1-x}}=\sum _{k=0}^{n}x^{k}=1+x+x^{2}+\dots +x^{n}$	1 if $k\leq n$; 0 otherwise
${\frac {1}{1-x}}=\sum _{k=0}^{\infty }x^{k}=1+x+x^{2}+\dots$	$1$
${\frac {1}{1-ax}}=\sum _{k=0}^{\infty }a^{k}x^{k}=1+ax+a^{2}x^{2}+\dots$	$a^{k}$
${\frac {1}{1-x^{r}}}=\sum _{k=0}^{\infty }x^{rk}=1+x^{r}+x^{2r}+\dots$	1 if $r$ divides $k$; 0 otherwise
${\frac {1}{(1-x)^{2}}}=\sum _{k=0}^{\infty }(k+1)x^{k}=1+2x+3x^{2}+\dots$	$k+1$
${\frac {1}{(1-x)^{n}}}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}\,x^{k}=1+{\binom {n}{1}}\,x+{\binom {n+1}{2}}\,x^{2}+\dots$	${\binom {n+k-1}{k}}={\binom {n+k-1}{n-1}}$
${\frac {1}{(1+x)^{n}}}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}\,(-1)^{k}x^{k}=1-{\binom {n}{1}}\,x+{\binom {n+1}{2}}\,x^{2}-\dots$	$(-1)^{k}{\binom {n+k-1}{k}}=(-1)^{k}{\binom {n+k-1}{n-1}}$
${\frac {1}{(1-ax)^{n}}}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}\,a^{k}x^{k}=1+{\binom {n}{1}}\,ax+{\binom {n+1}{2}}\,a^{2}x^{2}+\dots$	${\binom {n+k-1}{k}}a^{k}={\binom {n+k-1}{n-1}}a^{k}$
$\mathrm {e} ^{x}=\sum _{k=0}^{\infty }{\frac {x^{k}}{k!}}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\dots$	${\frac {1}{k!}}$
$\ln {(1+x)}=\sum _{k=0}^{\infty }{\frac {(-1)^{k+1}}{k}}\,x^{k}=x-{\frac {x^{2}}{2}}+{\frac {x^{3}}{3}}-{\frac {x^{4}}{4}}+\dots$	${\frac {(-1)^{k+1}}{k}}$

Example

$A=\left\{1,1,{\frac {1}{2!}},{\frac {1}{3!}},\ldots \right\}$ has a generating function of:

$\sum _{k=0}^{\infty }{\frac {x^{k}}{k!}}=e^{x}$

Extended Binomial Coefficient

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

Therefore

1. $(1+x)^{-n}=\sum _{k=0}^{\infty }{\binom {-n}{k}}x^{k}=\sum _{k=0}^{\infty }(-1)^{k}{\binom {n+k-1}{k}}x^{k}$
2. $(1-x)^{-n}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}x^{k}$

Applications of Generating Functions

Used to find the number of $r$-combinations from a set with $n$ elements where repetitions are allowed.

Example

Let $A=(a_{0},a_{1},\ldots )$ be a sequence (repetition allowed) with $a_{r}$ $r$-combintations.

$G(x)=\sum _{k=0}^{\infty }a_{k}x^{k}$

Since we can select any number of a particular element of the set when repetitions are allowed. Each element contributes $(1+x+x^{2}+\dots )$ to the product expansion of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(x)} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(x) = (1+x+x^2+\dots)^n = \frac{1}{(1-x)^n} = (1-x)^{-n} = \sum_{k=0}^\infty \binom{n+k-1}{k} x^k}

Example

Proposition. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^\infty \binom{n}{k}^2 = \binom{2n}{n}}

Proof. Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle\binom{2n}{n}} is the coefficient of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^n} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+x)^{2n}} , it must coincide with the coefficient of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^n} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+x)^n(1+x)^n = \left[ \textstyle\binom{n}{0} + \binom{n}{1}x+\dots+\binom{n}{n}x^n\right]^2} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle\binom{n}{0} \binom{n}{n} + \binom{n}{1} \binom{n}{n-1} + \dots + \binom{n}{n} \binom{n}{0}} is the coefficient of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^n} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+x)^n(1+x)^n} , so the proposition must be true since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle\binom{n}{k} = \binom{n}{n-k}} .

Q.E.D.