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

${\binom {u}{k}}={\begin{cases}{\frac {u(u-1)(u-2)\dots (u-k+1)}{k!}}&k>0\\1&k=0\end{cases}}$

Example

${\binom {-2}{3}}={\frac {(-2)(-3)(-4)}{3!}}=-4$

Extended Binomial Theorem

$(1+x)^{u}=\sum _{k=0}^{\infty }{\binom {u}{k}}x^{k}$

Footnotes

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