Transcript Advanced Counting

Recurrence Relations (RRs)
A “Recurrence Relation” for a sequence {an} is an equation
that expresses an in terms of one or more of the previous
terms in the sequence (i.e., a0,a1,a2,…,an-1) for all n≥n0.
Examples:
a0=1, a1=3, a2=4;
for n ≥3, an= an-1+an-2-an-3
1,3,4,6,7,9,10,12,13,15,16,18,19,21,22,…
a0=2, a1=4, a2=3;
for n ≥3, an= an-1+an-2-an-3
2,4,3,5,4,6,5,7,6,8,7,9,8,10,9,11,…
a0=4, a1=3, a2=3;
for n ≥3, an= an-1+an-2-an-3
4,3,3,2,2,1,1,0,0,-1,-1,-2,-2,-3,-3,-4,-4,…
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -1
Solutions to Recurrence Relations
A sequence {an} is called a “solution” of the recurrence
relation if its terms satisfy the recurrence relation.
Examples:
For n ≥3, an= an-1+an-2-an-3; Initial conditions: a0=1, a1=3, a2=4.
Solution: 1,3,4,6,7,9,10,12,13,15,16,18,19,21,22,…
For n ≥3, an= an-1+an-2-an-3; Initial conditions: a0=2, a1=4, a2=3.
Solution: 2,4,3,5,4,6,5,7,6,8,7,9,8,10,9,11,…
For n ≥3, an= an-1+an-2-an-3; Initial conditions: a0=4, a1=3, a2=3.
Solution: 4,3,3,2,2,1,1,0,0,-1,-1,-2,-2,-3,-3,-4,-4,…
Every recurrence relationship has many solutions
each determined uniquely by its own initial conditions.
We say a function f:N→R is a “solution” to a recurrence
relation if the sequence {f(n)} is a solution to it.
Example: f(n)=5 ∙2n is a solution to the recurrence relation an=2∙an-1.
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -2
Solving Recurrence Relations
If an=4an-1 and a0=3, find a function f such that f(n)=an.
an=4an-1=42an-2=43an-3=...=4na0=34n.
If an=an-1+n and a0=4, find a function f such that f(n)=an.
an=an-1+n=an-2+n+(n-1) =an-2+n+(n-1)+(n-2)=...
=a0+n+(n-1)+(n-2)+...+1=4+n(n+1)/2=(n2+n+8)/2.
If an=2nan-1 and a0=5, find a function f such that f(n)=an.
an=2nan-1=22n(n-1)an-2=23n(n-1)an-3=...=2nn!a0=5 2nn!.
If an=2an-1+1 and a0=0, find a function f such that f(n)=an.
an=2an-1+1=22an-2+2+1=23an-3+4+2+1=24an-4+8+4+2+1=...
=2n-1+2n-2+2n-3+...+8+4+2+1=2n-1.
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -3
Modeling with Recurrence Relations
An initial deposit of P0 dollars deposited at 7% annual interest.
Pn=(1+0.07)Pn-1 is the value after n years. Pn=(1+0.07)nP0
Rabbits on an island. Each pair producing a new pair every month.
Fibonacci Numbers: f0=0, f1=1; for n ≥2, fn= fn-1+fn-2.
Tower of Hanoi
Disks of decreasing diameter on 1 of 3 pegs.
Move disks to another peg, always maintaining
decreasing disk diameters on each peg.
Hn = number of moves to transfer n disks from 1 peg to another.
H1=1; for n ≥2, Hn= Hn-1+1+Hn-1 = 2Hn-1+1.
1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,
Hn= 2n-1.
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -4
RRs for Counting Bit Strings
How many bit strings of length n do not contain 2 consecutive 0’s?
b1=2 ({0,1}), b2=3 ({01,10,11})
For n ≥2: 01counted or 1counted
bn = bn-2
+
bn-1 .
Recognize this?
How many bit strings of length n contain 2 consecutive 0’s?
b0=b1=0
For n ≥2: 00any or 01counted or 1counted
bn = 2n-2
+ bn-2
+ bn-1 .
How many bit strings of length n contain 3 consecutive 0’s?
b0=b1=b2=0
For n ≥3: 000any or 001counted or 01counted or 1counted
bn = 2n-3
+ bn-3
+ bn-2
+ bn-1 .
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -5
Counting Code Words
How many strings of n digits have an even number of 0’s?
a1=9
For n ≥2:
Either the first digit isn’t 0 and the rest has an even
number of 0’s (there are 9an-1 of these)
or the first digit is 0 and the rest does not have an even
number of digits (there are 10n-1-an-1 of these)
an = 9an-1+(10n-1-an-1)=8an-1+10n-1
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -6
Catalan Numbers
Cn = number of ways to parenthesize the product of n+1 numbers.
C1=1: (1x2);
C2=2: (1x(2x3)), ((1x2)x3)
C3=5: (1x(2x(3x4))), (1x((2x3)x4)), ((1x2)x(3x4)), ((1x(2x3))x4), (((1x2)x3)x4)
C0=C1=1
Cn=C0Cn-1+C1Cn-2+C2Cn-3+…+Cn-3C2+Cn-2C1+Cn-1C0
Cn  k 0 Ck Cnk 1  C (2n, n) /( n 1) (Covered in Sec.7.4, Ex.41)
n 1
Cn = Number of extended
binary trees with n internal
nodes.
2
5
14
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -7
Solving Recurrence Relations
We’ve seen several examples of Recurrence Relations
an= a∙an-1
bn= n∙bn-1
fn =fn-2 +fn-1
bn=2n-2+bn-2+bn-1
bn=2n-3+bn-3+bn-2+bn-1 .
bn= bn-1+bn-2-bn-3
Hn=2Hn-1+1
In each case, many sequences satisfy the relationship and one also
needs to set/have initial conditions get a unique solution.
In some cases, we also have nice (“closed form”) function, f, for the
sequence, giving the nth term in a formula that doesn’t depend on
earlier ones, making it so that the sequence is just {f(n)}.
(For example, an=an and Hn=2n-1.)
We look at some classes of recurrence relations where we can do this.
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -8
Recurrence Relations
When c1, c2, …, ck are constants and ck≠0,
an= c1an-1+c2an-2+…+ckan-k +F(n)
is said to be a linear recurrence relation of degree k with
constant coefficients .
Linear = each aj appears only to the 1st power, no aj2 , aj3, . . .
degree k = k previous terms, ck≠0.
constant coefficients = cj are constants, not functions cj(n).
Additionally, if F(n)=0, the relation is called homogeneous.
Homogeneous linear recurrence relation of degree k with
constant coefficients:
an= c1an-1+c2an-2+…+ckan-k where ck≠0
We like these because we can solve them explicitly. 
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -9
Examples of Recurrence Relations
HLRRwCC =
Homogeneous linear recurrence relation with constant coefficients
an= a∙an-1
HLRRwCC of degree 1
an= (an-1)2
Not Linear
an= n∙an-1
Coefficients are not constant
fn =fn-2 +fn-1
HLRRwCC of degree 2
bn=2n-2+bn-2+bn-1 .
Not Homogeneous
bn=2n-3+bn-3+bn-2+bn-1 Not Homogeneous
an= an-1+an-2-an-3
HLRRwCC of degree 3
Hn=2Hn-1+1
Not Homogeneous
Remember:
A recurrence relation has many solutions.
Only when the initial conditions are specified is the solution unique.
For degree k, you need k contiguous initial conditions.
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -10
Solving Linear (degree 1) HLRRwCC
The relation is
an= c∙an-1
All solutions are of the form
an= d∙cn
The function is fd(n)= d∙cn
With the initial condition a0 specified, the unique solution is
an= a0cn
We saw this in computing compound interest
An initial deposit of P0 dollars deposited at 7% annual interest.
Pn=(1+0.07)Pn-1 is the value after n years.
Pn=(1+0.07)nP0
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -11
Fibonacci Solved
When we had the HLRRwCC of degree 1, f(n)=c∙f(n-1), we had such
good luck with fd(n)= d∙cn , let’s try F(n)=rn on the Fibonacci numbers
where we have the HLRRwCC of degree 2: F(n)=F(n-1)+F(n-2).
If we have F(n)=rn and F(n)=F(n-1)+F(n-2), then r2=r+1.
There are actually 2 solutions to this: r1=(1+√5)/2 and r2=(1-√5)/2
Letting Fi(n)= ri n (for i=1,2), we have
Fi(n-1)+Fi(n-2) = ri n-1+ri n-2 = ri n-2(ri +1) = ri n-2ri 2 =ri n = Fi(n)
which is just what we want except we also want F(0)=0 and F(1)=1.
Combining our 2 solutions (see lemma below) as F(n)=d1∙F1(n)+d2∙F2(n),
we get 0=d1+d2 and 1=d1∙r1+d2∙r2 ,and so 1=d1∙(r1-r2 )=d1∙(√5)
Giving the Fibonacci numbers as
((1  5 ) / 2) n  ((1  5 ) / 2) n
fn 
5
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -12
Solutions to HLRRwCC
We like HLRRwCC because we can solve them explicity.
That is, we can find functions f:N→R so that the
sequence {f(n)} solves/satisfies the recurrence relation.
Here’s part of the reason why.
Lemma: If functions f and g are solutions to the HLRRwCC
an= c1an-1+c2an-2+c3an-3+…+ckan-k
then f+g is also a solution as is d∙f for any constant d.
Definitions:
The characteristic equation of this HLRRwCC is
rk= c1rk-1+c2rk-2+c3rk-3+…+ck-1r+ck
The solutions (roots) of this equation are called the
characteristic roots of the recurrence relation
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -13
(Fibonacci) Degree 2 HLRRwCC
1) Write out the characteristic equation. (For Fibonacci: r2=r+1)
2) Find the characteristic roots (r1 and r2).
3) Any/Every function of the form f(n)=d1∙r1 n +d2∙r2 n
(d1 and d2 constants) satisfies/solves the recurrence relation.
4a) If the characteristic roots are distinct, we can pick d1 and d2 to
produce the required initial values.
4b) If there is only 1 characteristic root (r1=r2=r1),
then any/every function of the form f(n)=(d1+d2∙n)∙r n
(d1 and d2 constants) satisfies/solves the recurrence relation.
Example:
a0=1, a1=4; for n ≥2, an= 4an-1-4an-2
1,4,12,32,80,192,448,
Characteristic Equation: r2=4r-4  r2-4r+4=0  r=2 (twice)
f(n)=(d1+d2∙n)∙2 n & 1=d1 & 4=2d1+2d2  d1=d2=1;
f(n)=(1+n)∙2n and checking (“just for fun”) f(6)=(1+6)∙26=7∙64=448
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -14
All Solutions For Any HLRRwCC
Thrm: If rk= c1rk-1+c2rk-2+…+ck-1r+ck (ck≠0) has k distinct roots, r1,r2,…,rk,
then every solution of the recursion relation
an=c1an-1+c2an-2+…+ckan-k has the form
an= d1r1n+d2r2n+…+dkrkn for some d1, d2, …, dk
and every such sequence solves/satisfies the recursion relation.
If there are t distinct roots, each with multiplicity mi,
the sequences {an} solving the recursion relation are given by
an  (d1,0  d1,1n  ...  d1,m1 1n m11 )r1n
 (d 2,0  d 2,1n  ...  d 2, m2 1n m 21 )r2 n
 .....
 (dt ,0  dt ,1n  ...  dt ,mt 1n mt 1 )rt n
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -15
Degree 3 HLRRwCC Examples
a0=2, a1=5, a2=15; for n ≥3, an= 6∙an-1-11∙an-2- 6∙an-3
r3= 6∙r2-11∙r-6  r3-6∙r2+11∙r+6=0  (r-1)(r-2)(r-3)=0
General solution: an= x∙1n+y∙2n+z∙3n .
Initial values: 2=x+y+z; 5=x+2y+3z; 15=x+4y+9z  x=1; y=-1; z=2
Specific solution: an= 1-2n+2∙3n .
a0=1, a1=-2, a2=-1; for n ≥3, an= -3∙an-1-3∙an-2-an-3
r3= -3∙r2-3∙r-1  r3+3∙r2+3∙r+1=0  (r+1)3=0  r=-1 with multiplicity 3
General solution: an=(x+y∙n+z∙n2)∙(-1)n .
Initial values: 1=x; 2=x+y+z; -1=x+2y+4z  x=1; y=3; z=-2
Specific solution: an= (1+3n-2n2) (-1)n.
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -16
Inhomogeneous Recurrence Relations
Thrm: If f:N→R is any solution to the recurrence relation
an= c1an-1+c2an-2+…+ckan-k+F(n)
(1)
and g:N→R is a solution to the corresponding homogeneous RR
an= c1an-1+c2an-2+…+ckan-k
(2)
then f-g his also a solution to (1).
Moreover, if h:N→R is a solution to (1) then, f-h is a solution to (2).
Thrm: With (1) and (2) as above, if F(n) has the form
F(n)=(btnt+bt-1nt-1+ . . .+b1n+b0) sn
then there is a particular solution to (1) of the form
nm(ptnt+pt-1nt-1+ . . .+p1n+p0) sn
where m is the multiplicity of s as a characteristic root of (2)
and m=0 if s is not such a root.
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -17
Inhomogeneous RR Example
To Solve: an= 3∙an-1+2∙n; a1=3
an= 3∙an-1 has as its general solution an= c∙3n
F(n)=2n.
We take s=1 and look for a solution of the form f(n)=bn+d
an= 3∙an-1+2∙n  bn+d=3(b(n-1)+d)+2n
 2n(b+1)+(2d-3b)=0  Pick b=-1, d=3b/2=-3/2
f(n)=-n-3/2 is one solution and/but its initial value is -5/2
(we get the sequence -5/2, -7/2, -9/2, -11/2, . . .)
General solution: an = c∙3n-n-3/2
Initial condition: 3 = a1= c∙3-1-3/2 = 3c-5/2  c=11/6
Specific solution: an = -(2n+3-11∙3n-1)/2
UCI ICS/Math 6A, Summer 2007
[email protected]
9-AdvancedCounting -18