1
$\begingroup$

We can label the terms in a sequence as $a_n$ for the $n$th term. Then the generating function for the sequence can be defined as $ A(x) = \sum_{n=0}^\infty{a_n x^n} $

If we have a closed form for the resulting sum (meaning no summations, just an expression for the sum itself), I wish to know if it's known how to do a specific type of mapping, with certain operations. Specifically, for arbitrary $c$ and $d$, can we find the generating function $ B(x) = \sum_{n=0}^\infty{a_{(c\cdot n+d)} x^n} $

I'm wondering if it's known how to do this with arithmetic operations only. The main idea is to avoid calculus (such as integrals, differentials, and limits) as well as avoiding rewriting of variables (such as letting $x=x y$), and hopefully even avoiding summations (just using sums instead). I ask this because if we could perform this with arithmetic, it could be repeated like another recursion, and we should be able to get a closed form as a result.

So to recap, can we map $a_n \to b_n=a_{(c\cdot n+d)}$ using only arithmetic? Also, if we can't, what would we be able to do if we could?

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/4351/discussion-between-matt-groff-and-qiaochu-yuan)2012-08-01

1 Answers 1

3

Say $c$ is a positive integer and $d$ an integer. We'll also suppose that $0 \leq d < c$ (if it isn't, we can multiply the generating function by some appropriate power of $x$ and then it will be).

Let $B_{c,d}(x)=\sum_{n=0}^\infty a_{cn+d} x^n$, and let $\omega$ be a $c^{\rm th}$ root of unity. Then, if $0 \leq k < c$, we have $ A(\omega^k x) = \sum_{n=0}^\infty \omega^{nk} a_n x^n = \sum_{n=0}^\infty \sum_{d=0}^{c-1} \omega^{kd} a_{cn+d} x^{cn+d} \, ; $ after switching the order of summation, this becomes $ A(\omega^k x)=\sum_{d=0}^{c-1} \omega^{kd} x^d B_{c,d}(x^c) \, .$

This gives us $c$ linear equations in the $c$ unknowns $x^dB_{c,d}(x^c)$, which we can solve. To make this solution easier, you can notice that these equations are saying $\{A(w^k x)\}_k$ is the discrete Fourier transform of $\{x^dB_{c,d}(x^c)\}_d$. By the formula for the inverse discrete Fourier transform, it follows that $ x^dB_{c,d}(x^c)=\frac{1}{c}\sum_{k=0}^{c-1} \omega^{k(c-d)} A(\omega^k x) $ and so $ B_{c,d}(x)= \frac{1}{c x^{d/c}} \sum_{k=0}^{c-1} \omega^{k(c-d)} A(\omega^k x^{1/c}) \, . $

Note that, since we're taking $c^{\rm th}$ roots, this last equation will definitely hold formally (in the ring $\Bbb{C}[[x^{1/c}]]$), but if you want it to hold analytically on some domain in $\Bbb{C}$ you'll probably have to be really careful about choosing branches of $x^{1/c}$ correctly.