### 2 videos in "Equivalence Relations and Partial Orders"

## Lecture 16: Recurrence equations, generating functions, and equivalence relations

Lecture 16: Recurrence equations, generating functions, and equivalence relations

5186 views, 1 rating - 01:37:19

Part of video series ArsDigita Discrete Math Course

More information about this course:

http://www.aduni.org/courses/discrete

Licensed under Creative Commons Attribution ShareAlike 2.0:

http://creativecommons.org/licenses/by-sa/2.0/

http://www.aduni.org/courses/discrete

Licensed under Creative Commons Attribution ShareAlike 2.0:

http://creativecommons.org/licenses/by-sa/2.0/

(
download video
)

Learn more about using generating functions and how they can solve counting problems.

- Lecture Notes - Lecture Notes from the course
- Problem Set 7 - A problem set with some problems from this lecture

- How do generating functions help solve recurrence equations?
- How do you find the closed form for Fibonacci numbers using a generating function?
- How many binary trees are there with n nodes?
- How many ways are there of placing n pairs of balanced parentheses?
- How many ways are there of associating n+1 square matrices in order to multiply them?
- Why are the number of binary trees, the number of ways of placing balanced parentheses, and the number of ways of associating square matrices equivalent or the same problem, which are Catalan numbers?
- What are equivalence relations?
- How are Taylor series used with generating functions in solving counting problems?

Generating functions are explained some more in this lesson. A lot of Algebra is done and many different ideas are brought together in getting a generating function for the closed form of the Fibonacci sequence. Some of the math gets really ugly. Also, three equivalent problems are shown to be the same. Taylor series also make an appearance in this lesson.