So I've been fiddling around with the cauchy product of sequences lately, and am curious about a little identity I've found (which I'm sure is ubiquitous in finite differences, as I can't be the only one to have thought of it). I have been having trouble proving it, but the idea is rather straight forward. I think I might have seen it somewhere before but can't find any literature on the subject through searches and am exhausted for a proof (even though I know it should be simple).

Consider a ring of sequences $a:\mathbb{N} \to \mathbb{C}$ endowed with the usual addition $+$ and the multiplication operator $\times$ where

$$(a \times b)(n) = \sum_{j=0}^n a_j b_{n-j}$$

The first identity, which at hand is very simple to prove, follows from associativity of the product. Firstly

$$(a \times 1)(n) = \sum_{j=0}^n a_j$$


I am correcting the terrible mistake I made

$$1 \times 1 \times ...(k\,times)...\times 1 = \dbinom{n+k-1}{k-1}$$

end of terrible mistake

giving the usual iterated sum formula

edited to not be a terrible mistake

$$\sum^k a(n) = (a\times \dbinom{n+k-1}{k-1})$$

$$\sum^k a(n) = \sum_{j=0}^n a_j\dbinom{n+k-1-j}{k-1}= \sum_{n_{k-1}=0}^n \sum_{n_{k-2}=0}^{n_{k-1}}...k\,times...\sum_{n_0=0}^{n_1} a(n_0)$$

where $\sum^{k}\sum^{j} = \sum^{k+j}$. The question I am curious about is if this has ever been investigated for complex numbers--i.e; does anyone have any references to the operator

$$\sum^{s} a = \sum_{j=0}^n a_j \dbinom{n+s-j-1}{s-1}$$

and if perhaps it satisfies the identity

$$\sum^{s} \sum^{q} = \sum^{s+q}$$

so that it forms a sort of differsum (like a differintegral but with sums). By associativity of the Cauchy product the semigroup property is equivalent to showing

edited to remove the typo $$\sum_{j=0}^n \dbinom{j+s-1}{s-1}\dbinom{n+q-j-1}{q-1} = \dbinom{n+s+q-1}{s+q-1}$$

which follows for $s,q \in \mathbb{N}$ (by the above) but I am unsure for $\Re(s),\Re(q) > 0$.

This is something I imagine must be somewhere in the vastness of literature on calculus of variations or finite differences. A proof or a reference to a proof is what I'm really looking for. I'm particular to a reference though, as I'd like to read what else people have written on the subject.

the typo was the whole problem to be honest, I just made a typo. /shameface

  • $\begingroup$ This is the discrete convolution, en.wikipedia.org/wiki/Convolution#Discrete_convolution In the particular case of sequences $u:\mathbb{Z}\to\mathbb{C}$ supported on $\mathbb{Z}_+$, it is also called "one-side convolution", and corresponds to the Cauchy product of power series. $\endgroup$ – Pietro Majer Nov 25 '16 at 19:56
  • $\begingroup$ @PietroMajer I'm well aware of that, I guess I didn't make myself clear enough. I was more interested in the properties of the iterated sum, and then the complex iterated sum. If this construction exists in literature somewhere. $\endgroup$ – user78249 Nov 25 '16 at 19:58
  • $\begingroup$ This fails when $n=0,$ right? $\endgroup$ – Pat Devlin Nov 25 '16 at 20:45
  • $\begingroup$ And this even fails for positive integers $s$ and $q$. Right? $\endgroup$ – Pat Devlin Nov 25 '16 at 20:50
  • 1
    $\begingroup$ Should it be $1\times\ldots\text{($k$ times)}\ldots\times 1 = {n+k-1\choose k-1}$? $\endgroup$ – Julian Rosen Nov 25 '16 at 23:18

Ok. Fixing the typo in the post, we can prove the claim without much trouble.

After fixing the typo, the question is really asking to prove the following for all nonnegative integers $n$ and all complex $s$ and $q$: $$ \sum_{k=0}^{n} {k+s-1 \choose k} {n-k + q-1 \choose n-k} = {n+q+s-1 \choose n}, $$ where ${z \choose n} = \frac{z(z-1)(z-2)\cdots (z-n+1)}{n!}$.

This is easy with generating functions. Define the formal power series $$G_s (x) = \sum_{n=0} ^{\infty} {n+s-1 \choose n} x^n.$$ Then the claim is the same as showing $G_s(x) G_q (x) = G_{s+q} (x).$ But this follows immediately from the fact that $$ G_s (x) = \sum_{n=0}^{\infty} {n+s-1 \choose n} x^n = \frac{1}{(1-x)^{s}}. $$

See this link for more.

  • $\begingroup$ I don't see how the OP's question is asking what you say it is really asking (which is a form of the well-known Chu-Vandermonde identity). But perhaps the OP should clarify what is meant by the expression $\binom{n}{s}$ (for complex $s$): is it $\frac{\Pi(n)}{\Pi(s)\Pi(n-s)}$ where $\Pi(s) := \int_0^\infty x^s e^{-x} dx$? $\endgroup$ – Todd Trimble Nov 26 '16 at 1:19
  • $\begingroup$ What he asked is false and not analogous with his convolution formula. His convolution formula is supposed to be that of my post when $s$ is a positive integer. In his notation, $1\times 1$ is supposed to have generating function $1/(1-x)^2$, but his didn't. $\endgroup$ – Pat Devlin Nov 26 '16 at 1:22
  • $\begingroup$ Even after fixing the typo, I still don't understand how this would answer the (fixed-up) question. Roughly speaking: how is an expression of type $\binom{\text{integer}}{s}$, by my reading a transcendental function in the complex variable $s$, supposed to relate to expressions of type $\binom{z}{\text{integer}}$ which are polynomials in $z$? $\endgroup$ – Todd Trimble Nov 26 '16 at 1:38
  • $\begingroup$ It's supposed to be ${n+s-1 \choose s-1} = {n+s-1 \choose n}$ $\endgroup$ – Pat Devlin Nov 26 '16 at 1:40
  • 1
    $\begingroup$ Well you at least get a winky face. Ty. ;) this made my day. $\endgroup$ – user78249 Nov 26 '16 at 6:19

Your Answer

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