Can any repeating sequence be expressed in a generating function?

104 Views Asked by At

Suppose we have a sequence $a$ with a repeating pattern of length $k$. For simplicity, we can express it as:

$$ a=\{c_0,c_1,...,c_{k-1},c_0,c_1,...\} $$

Where $a_n$ is the $n$th term, starting from $n=0$, can a generating function be found for such a sequence?

1

There are 1 best solutions below

1
On BEST ANSWER

Short Answer

Yes, we can turn any such pattern into the following OGF. $$ A(x)=\frac{c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+...+c_1x+c_0}{1-x^k} $$

Behind the Answer

Not that a repeating pattern is commonly used for a generating function, but if you have a repeating pattern such that is naively defined by a relationship with a previous index, it'll always have this format. Of course if you have a repeating sequence that's a bit less trivial it will have a different form, but this is just a proof that there must exist a generating function for any infinitely repeating sequence.

We can set a recurrence relation using $a_n$:

$$ a_{n+k}=a_n; a_0=c_0,a_1=c_1,...,a_{k-1}=c_{k-1} $$

We look to using an ordinary generating function (OGF) $A(x)$ for our purposes:

$$ A(x)=\sum_{n\geq0}a_nx^n $$

Note that with most generating functions, $x$ is just a dummy variable that needs to be algebraically upheld on some range of values with our manipulation.

$$ a_{n+k} = a_n $$ $$ a_{n+k}x^{n+k} = a_nx^{n+k} $$ $$ \sum_{n\geq0}a_{n+k}x^{n+k}=\sum_{n\geq0}a_nx^{n+k} $$ $$ \sum_{n\geq0}a_nx^n-a_{k-1}x^{k-1}-a_{k-2}x^{k-2}-...-a_1x-a_0=x^k\sum_{n\geq0}a_nx^n $$ $$ A(x)-c_{k-1}x^{k-1}-c_{k-2}x^{k-2}-...-c_1x-c_0=x^kA(x) $$ $$ A(x)-x^kA(x)=c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+...+c_1x+c_0 $$ $$ A(x)(1-x^k)=c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+...+c_1x+c_0 $$ $$ A(x)=\frac{c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+...+c_1x+c_0}{1-x^k} $$ And at this point since we've found an expression for $A(x)$ without the use of the recurrence so we'd be done. However, despite being potentially messier to get what you seek, I quite enjoy the ones below: $$ A(x)=\frac{\sum_{j=0}^{k-1}c_jx^j}{1-x^k}=\sum_{j=0}^{k-1}c_jx^j\sum_{n\geq0}x^{nk} $$