Solving Recursive Sequence using Generating Function

02/08/2019

I. Definition

Hàm sinh là cái hàm mà nén 1 dãy số $\{a_n\}, n\geq 0$ có quy luật thành một cái tổng $$\sum_{n=0}^\infty a_nx^n$$ Hệ số của $x^n$ chính là số hạng $a_n$ trong dãy $\{a_n\}, n\geq 0$.

II. Several Formulas Generating Function

III. Solving Recursive Sequence.

Examples:

This example is my friend ‘s question in his interview, so I just note it. Ngoài ra còn có hàm sinh mũ cũng giải các hệ thức đệ quy phức tạp hơn.

More about generating function: slide thầy Luyện HCMUS.
You can comment your example, i will try my best to solve it.