# What would be possible if we could perform repeated “linear mapping” on recurrences?

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?

-
$c$ has to be a positive integer, and $d$ an integer, right? –  Mercy Aug 1 '12 at 17:01
@Mercy: They don't have to be, but for the sake of the question you can assume so. –  Matt Groff Aug 1 '12 at 17:11
Depends on what you mean by "arithmetic." For example, the generating function for the even terms is $\frac{A(x) + A(-x)}{2}$. In general, look up the discrete Fourier transform. –  Qiaochu Yuan Aug 1 '12 at 17:31
@QiaochuYuan: That's kind of borderline, since it may result in something other than a closed form. I was wondering if we were to know a way to work strictly with closed forms, if that would bring about any new potential, and/or if that would be a worthwhile discovery. –  Matt Groff Aug 1 '12 at 17:45
You get a form which is just as much a closed form as $A(x)$ is. –  Qiaochu Yuan Aug 1 '12 at 17:46

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.