CSCE 222 Lecture 23

« previous | Friday, April 1, 2011 | next »

Solving the Fibonacci sequence

${\begin{aligned}f_{0}=0&=\alpha _{1}+\alpha _{2}\\f_{1}=1&=\alpha _{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{1}+\alpha _{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{1}\\f_{2}=1&=\alpha _{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{2}+\alpha _{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{2}\\\alpha _{1}&={\frac {1}{\sqrt {5}}}\\\alpha _{2}&=-{\frac {1}{\sqrt {5}}}\end{aligned}}$

Ruby Implementation

def fib n
  return 1 if n==0 or n==1
  fib(n-1) + fib(n-2)
end

This recursive function runs in $T(n)=1+T(n-1)+T(n-2)=\Theta ($ time.

In General

A polynomial of degree $k$ has $k$ distinct roots:

$r^{k}-c_{1}r^{k-1}+-c_{2}r^{k-2}-\dots -c_{k}=0\,\!$

A recursive function of degree $k$ written as

$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\dots +c_{k}a_{n-k}\,\!$

can be rewritten as a polynomial:

$a_{n}=\alpha _{1}r_{1}^{n}+\alpha _{2}r_{2}^{n}+\dots +\alpha _{k}r_{k}^{n}$

where $\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}$ are constants.

Generating Functions

A generating function for sequence $\{a_{n}\}_{n\geq 0}$ is the infinite series

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

Example

$\{a_{n}\}_{n\geq 0}$ with $a_{k}=2^{k}$ has the generating function

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

Example

$\{a_{n}\}_{n\geq 0}$ with $a_{k}=1$ (i.e. (1,1,…,1) ) has the generating function

$G(x)=\sum _{k=0}^{\infty }x^{k}=\left(1+x+x^{2}+x^{3}+\dots \right)={\frac {1}{1-x}}$

Theorem

Suppose we have two generating functions $f(x)=\textstyle \sum _{k=0}^{\infty }a_{k}x^{k}$ and $g(x)=\textstyle \sum _{k=0}^{\infty }b_{k}x^{k}$.

${\begin{aligned}f(x)+g(x)&=\sum _{k=0}^{\infty }(a_{k}+b_{k})x^{k}\\f(x)\cdot g(x)&=\sum _{k=0}^{\infty }\left(\sum _{j=0}^{\infty }a_{j}b_{k-j}\right)x^{k}\end{aligned}}$

Example

${\begin{aligned}{\frac {1}{1-x}}{\frac {1}{1-x}}&=\sum _{k=0}^{\infty }\left(\sum _{j=0}^{k}1\right)x^{k}\\&=\sum _{k=0}^{\infty }(k+1)x^{k}\end{aligned}}$

Extended Binomial Coefficient

Let $u$ be a real number and 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 k} be a nonnegative integer. (Factorials on 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 u} are out of the question.

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{u}{k} = \begin{cases} \frac{u(u-1)(u-2)\dots(u-k+1)}{k!} & k>0 \\ 1 & k=0 \end{cases}}

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 \binom{-2}{3} = \frac{(-2)(-3)(-4)}{3!} = -4}

Extended Binomial Theorem

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

Footnotes

Get The Art of Computer Progamming vol. 1-4a