Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.