Recurrence section 6.2 of unit 6 explained

dfdgfd

1. CSE 2813 Discrete Structures
Solving Recurrence Relations
Section 6.2

2. CSE 2813 Discrete Structures
Degree of a Recurrence
Relation
•The degreeof a recurrence relation is k
if the sequence {a
n} is expressed in
terms of the previous kterms:
a
nc
1a
n-1+ c
2a
n-2+ … + c
ka
n-k
where c
1, c
2, …, c
kare real numbers
and c
k0
•What is the degree of a
n2a
n-1+ a
n-2?
•What is the degree of a
na
n-2+ 3a
n-3?
•What is the degree of a
n3a
n-4?

3. CSE 2813 Discrete Structures
Linear Recurrence
Relations
•A recurrence relation is linearwhen a
n
is a sum of multiples of the previous
terms in the sequence
•Is a
na
n-1+ a
n-2linear ?
•Is a
na
n-1+ a
2
n-2linear ?

4. CSE 2813 Discrete Structures
Homogeneous
Recurrence Relations
•A recurrence relation is homogeneous
when a
ndepends only on multiples of
previous terms.
•Is a
na
n-1+ a
n-2homogeneous ?
•Is P
n(1.11)P
n-1homogeneous ?
•Is H
n2H
n-1+ 1homogeneous ?

5. CSE 2813 Discrete Structures
Solving Recurrence
Relations
•Solving 1
st
Order Linear Homogeneous
Recurrence Relations with Constant
Coefficients (LHRRCC)
–Derive the first few terms of the sequence using
iteration
–Notice the general pattern involved in the iteration
step
–Derive the general formula
–Now test the general formula on some previously
calculated (by iteration) terms

6. CSE 2813 Discrete Structures
Solving 2
nd
Order LHRRCC
•Form: a
nc
1a
n-1+ c
2a
n-2with some
constant values for a
0and a
1
•Assume that the solution is a
nr
n
,
where ris a constant and r0

7. CSE 2813 Discrete Structures
Step 1
•Solve the characteristic quadratic
equation r
2
–c
1r–c
2=0 to find the
characteristic roots r
1and r
22
4
2
2
11
2,1
ccc
r



8. CSE 2813 Discrete Structures
Step 2
•Case I: The roots are not equal
a
n= 
1r
1
n
+ 
2r
2
n
•Case II: The roots are equal (r
1=r
2=r
0)
a
n= 
1r
0
n
+ 
2nr
0
n

9. CSE 2813 Discrete Structures
Step 3
•Apply the initial conditions to the equations
derived in the previous step.
–Case I: The roots are not equal
a
0 = 
1r
1
0
+ 
2r
2
0
= 
1+ 
2
a
1 = 
1r
1
1
+ 
2r
2
1
= 
1r
1+ 
2r
2
–Case II: The roots are equal
a
0 = 
1r
0
0
+ 
20r
0
0
= 
1
a
1 = 
1r
0
1
+ 
21r
0
1
= (
1+
2)r
0

10. CSE 2813 Discrete Structures
Step 4
•Solve the appropriate pair of equations
for 
1and 
2.

11. CSE 2813 Discrete Structures
Step 5
•Substitute the values of 
1, 
2, and the
root(s) into the appropriate equation in
step 2 to find the explicit formula for a
n.

12. CSE 2813 Discrete Structures
Example
•Solve the recurrence relation:
a
n 4a
n-1 4a
n-2
where a
0 a
1 1
•Solve the recurrence relation:
a
n a
n-1 + 2a
n-2
where a
0 2 and a
1 7

13. CSE 2813 Discrete Structures
Exercises
•1, 3