Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
$c$ has to be a positive integer, and $d$ an integer, right? – Mercy King 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
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.