1

I would like to know more about constructing generating functions for certain type of sequences defined differently over certain ranges of $n$, and would appreciate any references.

For example, if there is a sequence:

$a_{n+1} = 3a_n$, the standard trick is to multiply both sides by $x^n$, and sum over all valid values of $n$.

However, I would like to know if there are any methods to find a generating function for something like: $ a_{n+1} = \left\{ \begin{array}{r l} 3a_n & n \leq K \\ 0 & n > K \end{array}\right. $ for some constant $K$. Or for example, $ a_{n+1} = \left\{ \begin{array}{r l} \frac{1}{n+1}a_n & n \leq K \\ K_1 & n > K \end{array}\right. $

To be more specific, are there any methods for problems like $ a_{n+1} = \left\{ \begin{array}{r l} f_1(n) a_n & n \leq K_1 \\ f_2(n) a_n & K_1 < n \leq K_2 \\ \vdots \end{array}\right. $ ?

Thanks!

user153781
  • 11

2 Answers2

2

Generating function is essentially the same thing as recurrence relation, so if the recurrence relation doesn't continue to infinity, your generating function loses some important properties because of the boundary where recurrence relation is interrupted. For the first example, the generating function can be derived as the following:

Let $$A(x)=\sum_{k=1}^{\infty}a_kx^k=\sum_{k=1}^{n}a_kx^k$$

Then, $$\sum_{k=1}^{n}a_{k+1}x^k=\sum_{k=1}^{\infty}3a_kx^k$$ $$\dfrac{A(x)-a_0}{x}+a_nx^n=3A(x)$$ $$A(x)=\dfrac{a_0-a_nx^{n+1}}{1-3x}$$

The second example can be also calculated in the same way. Refer to generatingfunctionlogy as mentioned by Batman. If you use "expansion method", truncate the terms $\{x^{n+1}, x^{n+2},...\}$ as mentioned by him.

For the third example, I don't have any idea of how to utilize generating function to tackle with such problem. Check some more advanced references such as Analytic Combinatorics Hardcover by Philippe Flajolet as well as generatingfunctionlogy.

Math.StackExchange
  • 3,712
1

A fantastic reference for this is Generatingfunctionology by Wilf.

In the first case, start with the generating function for $a_n$, $A(x)$. Then, the generating function for $3 a_n$ is $3 A(x)$. Expand it into a series and truncate after $K+1$. Most of the time though, you usually ignore that constant $K$ while doing the counting via generating functions, and then at the end look at coefficients in the generating function which give valid results.

Batman
  • 19,390