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 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} has 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} distinct roots:

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^k-c_1r^{k-1}+-c_2r^{k-2}-\dots-c_k = 0\,\!}

A recursive function of degree 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} written as

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_n=c_1a_{n-1}+c_2a_{n-2}+\dots+c_ka_{n-k}\,\!}

can be rewritten as a polynomial:

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_n=\alpha_1r_1^n+\alpha_2r_2^{n}+\dots+\alpha_kr_k^n}

where 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 \alpha_1,\alpha_2,\ldots,\alpha_k} are constants.

Generating Functions

A generating function for sequence 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_n\}_{n\ge0}} is the infinite 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 G(x)=\sum_{k=0}^\infty a_kx^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_n\}_{n\ge0}} 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_k=2^k} has the generating function

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 2^kx^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_n\}_{n\ge0}} 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_k=1} (i.e. (1,1,…,1) ) has the generating function

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 x^k = \left(1+x+x^2+x^3+\dots \right) = \frac{1}{1-x}}

Theorem

Suppose we have two generating functions 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 f(x) = \textstyle\sum_{k=0}^\infty a_kx^k} 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 g(x) = \textstyle\sum_{k=0}^\infty b_kx^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 \begin{align} 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_jb_{k-j} \right) x^k \end{align}}

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 \begin{align} \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{align}}

Extended Binomial Coefficient

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 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