Scribd
Upload
5 views2 pages

Discrete Mathematics Recurrence Worksheet

The document is a worksheet for Discrete Mathematics and Combinatorics from Dambi Dollo University, focusing on recurrence relations. It includes problems related to finding orders, terms, and characteristics of various recurrence relations, as well as verifying solutions to specific sequences. The worksheet covers multiple exercises aimed at understanding linearity, homogeneity, and characteristic equations.

Uploaded by

Gebisa Aba Sagale
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views2 pages

Discrete Mathematics Recurrence Worksheet

The document is a worksheet for Discrete Mathematics and Combinatorics from Dambi Dollo University, focusing on recurrence relations. It includes problems related to finding orders, terms, and characteristics of various recurrence relations, as well as verifying solutions to specific sequences. The worksheet covers multiple exercises aimed at understanding linearity, homogeneity, and characteristic equations.

Uploaded by

Gebisa Aba Sagale
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DAMBI DOLLO UNIVERSITY

College of Natural and Computational Science


Mathematics Department
Worksheet 2 for Discrete Mathematics and Combinatorics

1) Find the order and the first five terms of the following recurrence relations. Also determine if it is
linear with constant coefficients and homogeneous.

a) an = 6an−1 , a0 = 2
b) an = (an−1 )2 , a1 = 2
c) an = an−1 + 3an−2 , a0 = 1, a1 = 2
d) an = nan−1 + n2 an−2 , a0 = 1, a1 = 1
e) an = an−1 + an−3 , a0 = 1, a1 = 2, a2 = 0

2) Let an = 2n + 5.3n , f or n = 0, 1, 2, ...

a) Find a0 , a1 , a2 , a3 , and a4 .
b) Show that a2 = 5a1 − 6a0 , a3 = 5a2 − 6a1 , and a4 = 5a3 − 6a2 .
c) Show that an = 5an−1 − 6an−2 for all integers n with n ≥ 2.

3) Show that the sequence an is a solution of the recurrence relation an = −3an−1 + 4an−2 if

a) an = 0
b) an = 1
c) an = (−4)n
d) an = 2(−4)n + 3

4) Is the sequence an a solution of the recurrence relation an = 8an−1 − 16an−2 if

a) an = 0
b) an = 2n
c) an = n.4n
d) an = 2.4n + 3n.4n
e) an = (−4)n
f) an = n2 .4n
g) an = 1
h) an = (4)n

5) Find the characteristic equation and the characteristic roots of the recurrence relations and the solution
for them.

1
a) an = an−1 , a0 = 1
b) an = 3an−1 − 2an−2 , a0 = 1, a1 = 3
c) an = 6an−1 − 9an−2 , a0 = 1, a1 = 6
d) an = 6an−1 − 11an−2 + 6an−3 , a0 = 2, a1 = 5, a2 = 15
e) an = 7an−1 − 10an−2 , a0 = 4, a1 = 17
f) an = 8an−1 − 16an−2 , a2 = 16, a3 = 80

6) Find solutions for the recurrence relations

a) an = 10an−1 − 21an−2 + 5n
b) an = −5an−1 − 9, a0 = 6
c) an = 7an−1 − 10an−2 + 6 + 8n, a0 = 1, a1 = 2
d) an = 4an−2 + n2 + n − 1, a0 = 6, a1 = 10

You might also like