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

$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 $x_{1},x_{2},x_{3},\ldots ,x_{n}$

For $C_{n-1}$ if $x_{n}$ is a 0, then $x_{1},x_{2},\ldots x_{n-1}$ must be an arbitrary legal n-1 string. If $x_{n}$ is a 1, then $x_{1},x_{2},\ldots ,x_{n-1}$ must be a legal n-1 string that ends in a 1. This means that $x_{1},x_{2},\ldots ,x_{n-2}$ must be a valid n-2 strings (conforming to $C_{n-2}$).

$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 $x_{1},\ldots ,x_{n-k}$ must be a legal string, then add all of the $C_{n-k}$ cases to form the $C_{n}$case. If there is ever a case where $x_{1},\ldots ,x_{n-k}$ must be an illegal string, then subtract the number of legal strings from the number of total possibilities