It's well known that generating functions are great to solve recurence relations in form $$a_n = A*a_{n-1} + B*a_{n-2} + \dots$$

But i was wondering what happens if recurence relation contains division in subscripts? It is: $$a_n = A*a_{\lfloor \frac{n}{2} \rfloor} + B*a_{\lfloor \frac{n}{3} \rfloor} + \dots$$ where $A$ and $B$ are some contants. On this stage, let's ignore boundary cases (n=0, 1 etc.) and assume $A$ and $B$ are equal to $1$.

Noting $A(x)$ as generating function for sequence $<a_n>_{0}^\infty$ we have $$A(x) = (1+x)A(x^2) + (1+x+x^2)A(x^3)$$ if i understand it correctly.

I searched the internet for that and even Wilf's gfology book, but i couldn't find explaination for this case. Maybe we can't solve this recurence easily and in effect, can't have closed form for this recurence? Are there other tools to solve it? Thanks in advance.


Erdös et al, "The Asymptotic Behavior of a Family of Sequences" (Pacific Journal of Mathematics 126:2, pp 227-241, dec 1987, here a more readable version than the one in the journal) discuss exactly this type of sequences.

| cite | improve this answer | |

Intersting question, but I think, only constant sequences verify this. take $(a_n)$ a sequence verifying a recurrence equation :

$$a_n=\sum_{k=2}^r\lambda_ka_{\lfloor \frac{n}{k} \rfloor}$$

Then, evaluating it for $n=0$ we get :

$$a_0=\sum_{k=2}^r\lambda_ka_0 $$

That is either $a_0=0$ or :

$$\sum_{k=2}^r\lambda_k=1 $$

First, if $a_0=0$ then $a_1=a_0*=0$ and with a trivial induction you have that $a_n=0$ for all $n$.

Suppose now that $a_0\neq 0$ then we will show by induction that $a_n=a_0$. The case $n=0$ is trivial. Assume that $a_l=a_0$ for $0\leq l<n$ then for all $k\geq 2$ :

$$\lfloor \frac{n}{k} \rfloor <n$$

So by induction hypothesis :

$$a_{\lfloor \frac{n}{k} \rfloor}=a_0 $$

Finally :

$$a_n=\sum_{k=2}^r\lambda_ka_{\lfloor \frac{n}{k} \rfloor}=\sum_{k=2}^r\lambda_ka_0=a_0$$

If we add together all the pieces this shows that any function verifying a recurrence equation involving a division should be constant.

| cite | improve this answer | |
  • $\begingroup$ I am sorry to comment my own answer, but I feel I need to add something. Those kind of recurrence formula may appear when determining the number of partitions of $n$ with fixed summands (e.g. in sums of $2$, $3$). Maybe, if you want to go further with this you should clarify what you are asking as initial condition and specify that the equation is not verified for $n<n_0$ and is verified for $n\geq n_0$. In my mind I think $n_0=lcm(2,3,...,r)$ (with my notation). $\endgroup$ – Clément Guérin Apr 2 '15 at 8:28
  • $\begingroup$ You say $$\sum_{k=2}^r \lambda_k a_0 = a_0$$ That is not true when any $\lambda_k>1$. I understood $\lambda_k$ is constant standing next to $a_{\lfloor \frac{n}{k} \rfloor}$, right? $\endgroup$ – Krzysztof Lewko Apr 2 '15 at 8:38
  • $\begingroup$ Ok I get what you mean, actually this is related to my comment. If you want your recurrence equation to be true for any integer $n\geq 0$ then you are forced to have the equality : $$a_0=\sum_{k=2}^r\lambda_ka_0$$ And if any $\lambda_k>1$ this implies that $a_0=0$ (and then all the $a_i$'s are null as well). If you want to avoid this, you will have to say that the equation recurrence is not verified below some $n_0$ and then specify initial conditions $a_k:=...$ for $k<n_0$. $\endgroup$ – Clément Guérin Apr 2 '15 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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