# What are some “natural” interpolations of the sequence $\small 0,1,1+2a,1+2a+3a^2,1+2a+3a^2+4a^3,\ldots$?

(This is a spin-off of a recent question here)
In fiddling with the answer to that question I came to the set of sequences

$\qquad \small \begin{array} {llll} A(1)=1,A(2)=1+2a,A(3)=1+2a+3a^2,A(4)=1+2a+3a^2+4a^3, \ldots \\ B(1)=1,B(2)=1+3a,B(3)=1+3a+6a^2,B(4)=1+3a+6a^2+10a^3, \ldots \\ C(1)=1,C(2)=1+4a,C(3)=1+4a+10a^2,C(4)=1+4a+10a^2+20a^3, \ldots \\ \ldots \\ \end{array}$
with some indeterminate a .

We had the discussion often here in MSE, that interpolation to fractional indexes, say A(1.5)=?? is arbitrary, considering, that an initial solution composed with any 1 -periodic function satisfies the condition. But here the embedding in a set of sequences, which are constructed from binomial-coefficients might suggest some "natural" interpolation, such as for

$\qquad \small K(1)=1, K(2)=1+a, K(3)=1+a+a^2, \ldots$

the interpolation $\small K(r) = {a^r-1 \over a-1}$ seems the most "natural" which even can smoothly be defined for a=1. This observation made me to refer to "q-analogues" $\small [r]_a$ in my answer in the initiating MSE-question, but it's not obvious how to interpolate the shown sequences of higher orders A , B , C (I think they're not related to the "q-binomial-analogues" , for instance ).

Q: So what would be some "natural" interpolation to fractional indexes for the sequences A, B, C, and possibly in general for sequences generated in the obvious generalized manner?

Agreeing mostly with Henning's ansatz I got now the general form as
$$A_m(n) = {1 \over (1-a)^m} - \sum_{k=0}^{m-1} \binom{n+m}{k}{a^{n+m-k} \over (1-a)^{m-k} }$$ I do not yet see, whether some examples of fractional indexes agree with the solutions of all three given answers so far, for instance: given a=2.0 what is A(1.5), B(4/3), C(7/5)? With my programmed version I get now $\qquad \small A(1.5)\sim 9.48528137424$
$\qquad \small B(4/3) \sim 11.8791929545$
$\qquad \small C(7/5) \sim 18.4386165488$
(No interpolation for fractional m yet)

[update 2] the derivative-versions of Sivaram and Michael arrive at the same values so I think, all versions can be translated into each other and mutually support each other to express a "natural" interpolation. [update 3] I had an index-error in my computation call. Corrected the numerical results.

-

Here is an attack leading to a closed forms for the $A$s and $B$s that can be evaluated for fractional $n$:

First, let $A_n = \sum_{k=0}^n (k+1)a^k$. For $n>0$ we can write $$A_n = a A_{n-1} + 1 + a + \cdots + a^n = a A_{n-1} + \frac{a^{n+1}-1}{a-1}$$ We can then use a base case of $A_0=1=\frac{a-1}{a-1}$ to unfold the entire recurrence into \begin{align} A_n &= \frac{1}{a-1}\Bigl( (a^{n+1}-1) + a(a^n-1) + a^2(a^{n-1}-1) + \cdots + a^n(a-1) \Bigr) \\&= \frac{1}{a-1}\Bigl( (n+1)a^{n+1} - (1+a+\cdots+a^n) \Bigr) \\&= \frac{1}{a-1}\Bigl( (n+1)a^{n+1} - \frac{a^{n+1}-1}{a-1} \Bigr) \end{align}

We can push this into the $B$s by noting that $$B_n=A_n + a A_{n-1} + a^2 A_{n-2} + \cdots + a^n A_0$$ so \begin{align} B_n &= \frac{1}{a-1}\left(\sum_{k=0}^n k+1\right)a^{n+1} - \frac{1}{(a-1)^2} \Bigl( (a^{n+1}-1)+a(a^{n}-1)+\cdots+a^n(a-1) \Bigr) \\&= \frac{1}{a-1} \frac{(n+1)(n+2)}{2} a^{n+1} - \frac{1}{(a-1)^2} \Bigl( (n+1)a^{n+1} - (1+a+\cdots+a^n) \Bigr) \\&= \frac{1}{a-1} \frac{(n+1)(n+2)}{2} a^{n+1} - \frac{1}{(a-1)^2} (n+1)a^{n+1} + \frac{1}{(a-1)^3} (a^{n+1}-1) \end{align} A pattern is emerging ... I will leave the derivation for $C_n$ to the reader, but the only difficulty should be in keeping the algebra straight.

-
The alternating signs in the $B_n$ formula smell like there's some combinatoric inclusion-exclusion argument hiding somewhere beneath all this... or else I should just have written the denominators in terms of $1-a$ instead of $a-1$. Would it make any sense to treat the $a$ as a probability, I wonder? –  Henning Makholm Dec 3 '11 at 22:58
Henning, I started slightly differently but now arrived at that same type of expressions. The general form should then be a sum, and the (1-a)-version indeed seems to be preferable as you suggested. I'll put that form into the question-box. –  Gottfried Helms Dec 3 '11 at 23:18
One (cosmetic) problem with using $1-a$ is that then all of the terms become negative which looks strange. I think this approach should let you interpolate between, asy $C_{41}$ and $C_{42}$. Futher interpolation between $C_{41.7}$ and $D_{41.7}$ is a different matter, of course. –  Henning Makholm Dec 3 '11 at 23:28
Well, the cosmetic problem can be explained easily. Remember, that the expansion of 1/(1-a) is the geometric series of a written beginning at 1 along increasing powers out to infinity. From this the infinite tail is cutted by the subtraction, such that the finite leading part remains. Another problem becomes then visible: what does it then mean when a>1 ? Analytic continuation required? –  Gottfried Helms Dec 3 '11 at 23:50
Nice general form. For any $a\ne 1$ the closed-form expressions here can just be evaluated, no analytic continuation needed. The case $a=1$ probably needs to be special-cased -- for integer $n$ it should be something like $\binom{n+C}{m+1}$ for some small $C$, which generalizes easily to fractional $n$. But it's not clear to me that it will then be continuous for $a$ on the $a=1$ line (except for integral $n$, of course). –  Henning Makholm Dec 4 '11 at 0:09

You have $K(r) = (a^r-1)/(a-1)$.

And ${d \over da} K(r) = 1 + 2a + \cdots + (r-1)a^{r-2} = A(r-1)$.

So it seems natural to define $A(r) = {d \over da} K(r+1)$, where $K(r)$ is defined as in your interpolation.

Similarly $${d^2 \over da^2} K(r) = 2 B(r-2)$$ and $${d^3 \over da^3} K(r) = 6 C(r-3)$$ which we can solve for $B(r), C(r)$ to get $$B(r) = {1 \over 2} {d^2 \over da^2} K(r+2), C(r) = {1 \over 6} {d^3 \over da^3} K(r+3).$$

So I would define $$A_n(r) = {1 \over n!} {d^n \over da^n} K(r+n)$$ for any integer $n$ and real number $a$; this seems to be reasonably well-behaved. Here $A_1, A_2, A_3$ are your $A, B, C$.

(While I was writing this answer, Sivaram Ambikasaran's answer agreed. I am not sure if this is the same generalization or not.)

Also, does this extend to fractional $n$? I am not familiar enough with the fractional calculus to tell.

-
the "fractional n" (in the now extended question above this is the index m) makes me curious. I'm currently following Henning's explicite formula (with a slightly changed index n) and I'll try to get a clue how m could be interpolated in that framework. –  Gottfried Helms Dec 3 '11 at 23:45
Michael, after a handful of checks this derivative-formulation seems to agree with that other (explicite) formulation which I'd inserted in the original question. I just did numerical differentation with some fractional values n (in my notation, r in your notation here), so the methods seem to agree and so seem to mutually improve their application as candidates for the most "natural" concept of interpolation. Hmm. –  Gottfried Helms Dec 4 '11 at 0:18
Yes, what you have can definitely be made to work for arbitrary $n$. See my answer. –  Ｊ. Ｍ. Apr 28 '12 at 16:26

One "natural" interpolation is along the following lines. $$A(n) = \sum_{k=1}^{n} ka^{k-1} = \frac{d K_n(a)}{da}$$ $$B(n) = \sum_{k=1}^{n} \frac{k(k+1)}{2}a^{k-1} = \frac1{2!} \frac{d^2 K_{n+1}(a)}{da^2}$$ $$C(n) = \sum_{k=1}^{n} \frac{k(k+1)(k+2)}{6}a^{k-1} = \frac1{3!} \frac{d^3 K_{n+2}(a)}{da^3}$$ A generic "natural" interpolation would be $\displaystyle A_m(n) = \sum_{k=1}^{n} \binom{k+m}{m+1} a^{k-1} = \frac1{(m+1)!} \frac{d^{m+1} K_{n+m}(a)}{da^{m+1}}$.

In our case, $A_0(n) = A(n)$, $A_1(n) = B(n)$, $A_2(n) = C(n)$ and so on...

-
thanks; but is it a misprint to have the n as suffix with the function K instead as an argument? This way I'm unsure whether I understand your evaluation correctly. –  Gottfried Helms Dec 3 '11 at 22:15

I'll build from Michael's work (thanks for doing the heavy lifting!) and start with

$$A_n(r)=\frac1{n!}\frac{\mathrm d^n}{\mathrm da^n} \frac{a^{r+n}-1}{a-1}$$

Let's switch back to the series representation, and swap summation and differentiation:

$$A_n(r)=\frac1{n!}\sum_{k=0}^{r+n-1} \frac{\mathrm d^na^k}{\mathrm d a^n}$$

and make a suitable replacement:

$$A_n(r)=\frac1{n!}\sum_{k=0}^{r+n-1} \frac{k!a^{k-n}}{(k-n)!}=\frac1{n!}\sum_{k=-n}^{r-1} \frac{(k+n)!a^k}{k!}=\frac1{n!}\sum_{k=0}^{r-1} \frac{(k+n)!a^k}{k!}$$

where a reindexing and removal of extraneous zero terms was done in the last two steps.

The result can then be expressed as:

$$A_n(r)=\frac{\mathrm{I}_{1-a}(n+1,r)}{(1-a)^{n+1}}=\frac{1-\mathrm{I}_a(r,n+1)}{(1-a)^{n+1}}$$

where $\mathrm{I}_z(r,n)$ is a regularized incomplete beta function.

\begin{align*} A_n(r)&=\frac{\mathrm{I}_{1-a}(n+1,r)}{(1-a)^{n+1}}\\ &=\frac{a^r}{(n+1)\mathrm{B}(n+1,r)}{}_2 F_1\left({{n+r+1, 1}\atop{n+2}}\mid1-a\right)\\ &=\binom{n+r}{n+1} {}_2 F_1\left({{1-r,n+1}\atop{n+2}}\mid1-a\right) \end{align*}

where the third one is derived from the second one through the Pfaff transformation. In particular, the third one gives the representation

$$A_n(r)=r\binom{n+r}{r}\sum_{k=0}^{r-1}\binom{r-1}{k}\frac{(a-1)^k}{n+k+1}$$

which is valid for arbitrary $n$ and nonnegative integer $r$.

Other hypergeometric representations can be derived.

-