3

The generating function for the alternating sequence of 1's and 0's is composed by taking $(e^x +e^{-x})/2$.

This approach does not work for when we want the alternation to be based on $mod$ $3$. For ordinary generating functions, the general form of an equation for a sequence which is periodically 1 taken $ mod$ $n$ would be $ (1-x^{n})^{-1} $. We cannot do the same for exponential generating functions.

I have considered the triangular numbers, since those are naturally done $ mod $ $3$, but once again I failed to appropriate it to building a decent analytic generating function.

Confused Soul
  • 698

2 Answers2

3

In general, if you have a formal power series $$f(x)=a_0+a_1x+a_2x^2+a_3x^3+\ldots$$ and you want to extract only the coefficients divisible by some $k$, you can use a trick with the $k^{th}$ roots of unity to cause cancellation at every other $k$. In particular, let $\zeta_{n,k}=e^{2\pi i\cdot n/k}$. The $k^{th}$ roots of unity are exactly $\zeta_{0,k},\zeta_{1,k},\ldots,\zeta_{k-1,k}$ and one has that $\zeta_{a,k}\cdot\zeta_{b,k}=\zeta_{a+b,k}$. It is relatively easy to show that $$\zeta_{0,k}^n+\zeta_{1,k}^n+\zeta_{2,k}^n+\ldots+\zeta_{k-1,k}^n=\begin{cases}k&\text{if }k\text{ divides }n\\0 &\text{otherwise} \end{cases}$$ Using this, one can figure out that if we define $$g(x)=\frac{1}k\cdot \left(f(\zeta_{0,k}x) + f(\zeta_{1,k}x)+f(\zeta_{2,k}x)+\ldots+f(\zeta_{k-1,k}x)\right)$$ we will have that the power series of $g$ is just the same as $f$, except with every term not divisible by $k$ removed. Whether or not we are considering this a generating function or exponential generating function is irrelevant to this argument.

Milo Brandt
  • 60,888
2

Here's a trick that works: Let $w$ be the primitive third root of unity. Then the real part of $w^k$ yields the sequence $1, -1/2, -1/2, 1, -1/2, -1/2,\dots$, which is almost what we want. Adding a second sequence to cancel the spurious $-1/2$'s solves the problem:

$$ \begin{eqnarray} \frac{1\cdot x}{0!}+\frac{0\cdot x}{1!}+\frac{0\cdot x}{2!}+\frac{1\cdot x}{3!}+\cdots & = & \frac{2}{3}\mathcal{Re}\left\{\sum_k \frac{(wx)^k}{k!}\right\} + \frac{1}{3}\sum_k \frac{x}{k!} \\ & = & \frac{2}{3}\mathcal{Re}\left\{e^{wx}\right\}+\frac{1}{3}e^x \\ & = & \frac{1}{3}\left(e^{wx}+e^{\bar{w}x} \right) + \frac{1}{3}e^x \end{eqnarray} $$

Yly
  • 15,292