Generating Functions and Formal Power Series

Today we discuss some generating functions.

Problem 1: Give a finite set of positive integers $T$. Let $\mathfrak{T}_n$ be the collection of sequences $(t_1,t_2,...,t_m)$, such that $\sum_{i=1}^m t_m=n$, and each $t_i\in T$. Let $a_n=|\mathfrak{T}_n|$ for $n\ge1$ and $a_0=1$, and $f(x)=\sum_{n=0}^{\infty}a_n x^n$. Find out what is $f(x)$ explicitly.

Solution: It is not hard to note the recursive relation $a_n=\sum_{t\in T} a_{n-t}$ for $n\ge1$, if we set $a_i=0$ for negative $i$. So that $f(x)=1+\sum_{t\in T} x^t f(x)$ and $f(x)=1/(1-\sum_{t\in T} x^t)$, which is a rational function.

Variantion 1: If $T$ is infinite, what would happen? Would $f(x)$ still be rational?

We first analyze simple cases. If $T=\mathbb{N}^+$, it is expected that $f(x)=1+\sum_{t=1}^{\infty} x^t f(x)=1+f(x) x/(1-x)$, so that $f(x)=(1-x)/(1-2x)=1+\sum_{n=1}^{\infty} 2^{n-1} x^n$. Indeed, in this case, counting the sequences amounts to divide a sequence of $n$ objects arbitrarily. You can choose to divide between the $i$th and $i+1$th for $1\ge i\ge n-1$, so in all $2^{n-1}$ choices, justifying the expansion.

I think it is equivalent to $f$ being rational.

Theorem: $\mathbb{Q}_p(t)\cap\mathbb{Q}[[t]]=\mathbb{Q}(t)$

It is very interesting that this theorem is used for the rationality of $\zeta$-functions for algebraic varieties, which is part of the Weil conjectures.