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:

$\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}}$
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 \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}	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 \binom{n+k-1}{k}a^k=\binom{n+k-1}{n-1}a^k}
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 \mathrm{e}^x = \sum_{k=0}^\infty \frac{x^k}{k!} = 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots}	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 \frac{1}{k!}}
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 \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}	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 \frac{(-1)^{k+1}}{k}}

Example

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\{1, 1, \frac{1}{2!}, \frac{1}{3!}, \ldots\right\}} has a generating function 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 \sum_{k=0}^\infty \frac{x^k}{k!} = e^x}

Extended Binomial Coefficient

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 \binom{-n}{r} = (-1)^r \binom{n+r-1}{r}}

Therefore

1. 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} = \sum_{k=0}^\infty \binom{-n}{k}x^k = \sum_{k=0}^\infty (-1)^k \binom{n+k-1}{k} x^k}
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 (1-x)^{-n} = \sum_{k=0}^\infty \binom{n+k-1}{k} x^k}

Applications of Generating Functions

Used to find the number 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 r} -combinations from a set with 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 n} elements where repetitions are allowed.

Example

Let 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 = (a_0, a_1, \ldots)} be a sequence (repetition allowed) with 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_r} 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 r} -combintations.

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) = \sum_{k=0}^\infty a_kx^k}

Since we can select any number of a particular element of the set when repetitions are allowed. Each element contributes 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+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.