CSCE 222 Lecture 23

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

Solving the Fibonacci sequence

$\begin{array}{rl}{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{array}$

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)=\mathrm{\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,\dots ,{\alpha }_k$ are constants.

Generating Functions

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

$G(x)=\sum _{k=0}^{\mathrm{\infty }}{a}_k{x}^k$

Example

$\{a_n{\}}_{n\ge 0}$ with $a_k=2^k$ has the generating function

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

Example

$\{a_n{\}}_{n\ge 0}$ with $a_k=1$ (i.e. (1,1,…,1) ) has the generating function

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

Theorem

Suppose we have two generating functions $f(x)={\sum }_{k=0}^{\mathrm{\infty }}{a}_k{x}^k$ and $g(x)={\sum }_{k=0}^{\mathrm{\infty }}{b}_k{x}^k$.

$\begin{array}{rl}f(x)+g(x)& =\sum _{k=0}^{\mathrm{\infty }}(a_k+b_k)x^k\\ f(x)\cdot g(x)& =\sum _{k=0}^{\mathrm{\infty }}\left(\sum _{j=0}^{\mathrm{\infty }}{a}_j{b}_{k-j}\right)x^k\end{array}$

Example

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

Extended Binomial Coefficient

Let $u$ be a real number and $k$ be a nonnegative integer. (Factorials on $u$ are out of the question.

$(\genfrac{}{}{0ex}{}{u}{k})=\{\begin{array}{ll}\frac{u(u-1)(u-2)\dots (u-k+1)}{k!}& k>0\\ 1& k=0\end{array}$

Example

$(\genfrac{}{}{0ex}{}{-2}{3})=\frac{(-2)(-3)(-4)}{3!}=-4$

Extended Binomial Theorem

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

Footnotes

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