MATH 302 Lecture 15

« previous | Wednesday, October 19, 2011 | next »

Fibonacci Sequence

Recursive definition

fib1 n

   | n == 0 = 0
   | n == 1 = 1
   | otherwise = fib1 (n-1) + fib1 (n-2)

Easy to describe, but very expensive to evaluate:

fib1(6) |- fib1(5) | |- fib1(4) | | |- fib1(3) | | | |- fib1(2) | | | | |- fib1(1) | | | | `- fib1(0) | | | `- fib1(1) | | `- fib1(2) | | |- fib1(1) | | `- fib1(0) | `- fib1(3) | |- fib1(2) | | |- fib1(1) | | `- fib1(0) | `- fib1(1) `- fib1(4)

  |- fib1(3)
  |  |- fib1(2)
  |  |  |- fib1(1)
  |  |  `- fib1(0)
  |  `- fib1(1)
  `- fib1(2)
     |- fib1(1)
     `- fib1(0)

Iterative definition

def fib2 n

 return 0 if n == 0
 return 1 if n == 1
 x,y=0,1
 1.upto(n-1) { x,y = y,x+y }
 y

end

Counting Problems

Towers of Hanoi

Moving disks from one peg to another, etc. Example: It takes 7 moves to shift 3 disks to another peg.

Conjecture: It takes $2^{n}-1$ moves to move $n$ disks

Let $H_{n}$ represent the number of moves for $n$ disks

Moving $n-1$ disks takes $H_{n-1}$ . Move the last disk to another peg, then move the $n-1$ pegs on top of it:

H_{n}=2H_{n-1}+1

Look at pattern of values for $n$ :

$n$	$H_{n}$
1	1
2	3
3	7
4	15

This supports the conjecture:

Proof by induction.

Basis step. $H_{1}=1=2^{1}-1$ true.

Inductive step. Assume that for some $k>0$ , $H_{k}=2^{k}-1$ . By the recurrence relation, we have

H_{k+1}=2H_{k}+1=2(2^{k}-1)+1=2^{k+1}-1

Proving the inductive step. The general result follows by the principle of mathematical induction.

Bit Strings

Count the number of bit strings of length $n$ with no consecutive zeros: $C_{n}$

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}	Possibilities
0	{} = 1
1	{1, 0} = 2
2	{11, 10, 01} = 3
3	{111, 110, 101, 011, 010} = 5
4	{1111, 1110, 1101, 1011, 0111, 1010, 0101, 0110} = 8

Constructing a Recurrence Relation

Given a string 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_1, x_2, x_3, \ldots, x_n}

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 C_{n-1}} if 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} is a 0, then 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_1, x_2, \ldots x_{n-1}} must be an arbitrary legal n-1 string. If 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} is a 1, then 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_1, x_2, \ldots, x_{n-1}} must be a legal n-1 string that ends in a 1. This means that 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_1, x_2, \ldots, x_{n-2}} must be a valid n-2 strings (conforming to 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 C_{n-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 C_n = C_{n-1} + C_{n-2},\quad C_0=1\quad C_1=2}

Count the number of possibilities for the last digit in the string. Get to a point 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 x_1, \ldots, x_{n-k}} must be a legal string, then add all of the 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 C_{n-k}} cases to form the 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 C_n} case. If there is ever a case 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 x_1, \ldots, x_{n-k}} must be an illegal string, then subtract the number of legal strings from the number of total possibilities