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
    $c$ has to be a positive integer, and $d$ an integer, right?2012-08-01
  • 0
    @Mercy: They don't have to be, but for the sake of the question you can assume so.2012-08-01
  • 1
    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.2012-08-01
  • 0
    @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.2012-08-01
  • 0
    You get a form which is just as much a closed form as $A(x)$ is.2012-08-01
  • 0
    @QiaochuYuan: I'm working on a way that is simpler than the DFT, for this particular task. It avoids summations completely - that's what I meant by closed form. It seems it would greatly ease calculations if it works. I'm wondering now, while I'm working on it, if it may help allow new possibilities.2012-08-01
  • 0
    That is a very stringent and unusual definition of closed form. You should have specified this in the original post.2012-08-01
  • 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.