I have encountered the following sequence of alternating sums of binomials and I am wondering whether there is a nicer way to write every element and/or are there some nice properties about it.
So, if you have any idea about it, please let me know.
First of all pick two positive natural numbers $n, r\in\mathbb{N}, 0<r<n$.
Then, for all $j$, $0\leq j\leq r$, define
$$a_j:=\sum_{i=0}^j(-1)^{i}\binom{j}{i}\binom{n-i-1}{r-i-1}$$
Note that, using the standard convention $0!=1$, the previous formula is defined also for $j=0$.
The sequence I am interested in is the sequence of these $(a_j)$'s, varying $n, r$ and obviously $j$.
In particular at some point I will sum over $j$.
So the first terms of this sequence are $$\begin{aligned} a_0&=\binom{n-1}{r-1}\\ a_1&=\binom{n-1}{r-1}-\binom{n-2}{r-2}\\ a_2&=\binom{n-1}{r-1}-2\binom{n-2}{r-2}+\binom{n-3}{r-3}\\ a_3&=\binom{n-1}{r-1}-3\binom{n-2}{r-2}+3\binom{n-3}{r-3}-\binom{n-4}{r-4}\\ a_4&=\binom{n-1}{r-1}-4\binom{n-2}{r-2}+6\binom{n-3}{r-3}-4\binom{n-4}{r-4}+\binom{n-5}{r-5}\\ \ldots \end{aligned}$$
As you can see, it is very elegant, so I think that someone already studied it, and probably it is related to some property of the Pascal's triangle.
Not a simplification, but a nice property: Let
$$a_{n,r,j}:=\sum_{i=0}^{j}(-1)^i\binom{j}{i}\binom{n-i-1}{r-i-1}\qquad0<r<n,\quad0\leq j\leq r$$
\begin{align} a_{n+1,r+1,j+1}&-a_{n+1,r+1,j}\\ =&\sum_{i=0}^{j+1}(-1)^i\binom{j+1}{i}\binom{n-i}{r-i}-\sum_{i=0}^{j}(-1)^i\binom{j}{i}\binom{n-i}{r-i}\\ =&(-1)^{j+1}\binom{n-j-1}{r-j-1}+\sum_{i=1}^{j}(-1)^i\left(\binom{j+1}{i}-\binom{j}{i}\right)\binom{n-i}{r-i}\\ =&-\sum_{i=0}^{j}(-1)^i\binom{j}{i}\binom{n-i-1}{r-i-1}=\\ =&-a_{n,r,j} \end{align}
The recursion formula $a_{n+1,r+1,j+1}-a_{n+1,r+1,j}=-a_{n,r,j}$ with $0\leq j<r\leq n$ is used to find a generating function $A(x,y,z)$ for $a_{n,r,j}$.
Note: Since we already know a formula for $a_{n,r,j}$ (see question above) my hope was to find an alternative, simpler formula but this wasn't the case. Nevertheless, it was a nice (and due to miscalculations sometimes cumbersome) training in calculation to rediscover the formula stated above.
We use the more natural range $r\leq n$ instead of $r<n$ (see question above) which simplifies the calculation for the generating function.
Let $$A(x,y,z):=\sum_{n \geq 1}\sum_{r=1}^{n}\sum_{j=0}^{r-1}a_{n,r,j}x^{j}y^{r}z^{n}$$ be the generating function for $a_{n,r,j}$ with $0\leq j<r\leq n$. According to the recursion formula above we get
\begin{align*} \sum_{n \geq 1}&\sum_{r=1}^{n}\sum_{j=0}^{r-1}a_{n+1,r+1,j+1}x^{j}y^{r}z^{n} -\sum_{n \geq 1}\sum_{r=1}^{n}\sum_{j=0}^{r-1}a_{n+1,r+1,j}x^{j}y^{r}z^{n}\\ &=-\sum_{n \geq 1}\sum_{r=1}^{n}\sum_{j=0}^{r-1}a_{n,r,j}x^{j}y^{r}z^{n}\\ \end{align*}
The RHS is simply: $-A(x,y,z)$. To calculate the LHS we split the task into two parts.
\begin{align*} \sum_{n\geq 1}&\sum_{r=1}^{n}\sum_{j=0}^{r-1}a_{n+1,r+1,j+1}x^{j}y^{r}z^{n}\\ &=\sum_{n\geq 2}\sum_{r=2}^{n}\sum_{j=1}^{r-1}a_{n,r,j}x^{j-1}y^{r-1}z^{n-1}\\ &=\frac{1}{xyz}\left(A(x,y,z)-\sum_{n\geq 2}\sum_{r=2}^{n}a_{n,r,0}y^{r}z^{n} -\sum_{n\geq 2}a_{n,1,0}yz^{n}-a_{1,1,0}yz\right)\\ &=\frac{1}{xyz}\left(A(x,y,z)-\sum_{n\geq 2}\sum_{r=2}^{n}\binom{n-1}{r-1}y^{r}z^{n} -\sum_{n\geq 2}yz^{n}-yz\right)\\ &=\frac{1}{xyz}\left(A(x,y,z)-\sum_{n\geq 1}\sum_{r=1}^{n}\binom{n}{r}y^{r+1}z^{n+1} -y\left(\frac{1}{1-z}-1-z\right)-yz\right)\\ &=\frac{1}{xyz}\left(A(x,y,z)-y\sum_{n\geq 1}z^{n+1}\left((1+y)^{n}-1\right) -y\left(\frac{1}{1-z}-1\right)\right)\\ &=\frac{1}{xyz}\left(A(x,y,z)-yz\left(\frac{1}{1-(1+y)z}-1\right)+yz\left(\frac{1}{1-z}-1\right)\right)\\ &\qquad-\frac{1}{xyz}\left(y\left(\frac{1}{1-z}-1\right)\right)\\ &=\frac{1}{xyz}A(x,y,z)-\frac{1}{x}\left(\frac{1}{1-(1+y)z}\right) \end{align*}
\begin{align*} \sum_{n\geq 1}&\sum_{r=1}^{n}\sum_{j=0}^{r-1}a_{n+1,r+1,j}x^{j}y^{r}z^{n}\\ &=\sum_{n\geq 2}\sum_{r=2}^{n}\sum_{j=0}^{r-2}a_{n,r,j}x^{j}y^{r-1}z^{n-1}\\ &=\frac{1}{yz}\left(A(x,y,z)-\sum_{n\geq 2}\sum_{r=2}^{n}a_{n,r,r-1}x^{r-1}y^{r}z^{n} -\sum_{n\geq 2}a_{n,1,0}yz^{n}-a_{1,1,0}yz\right)\\ &=\frac{1}{yz}\left(A(x,y,z)-\sum_{n\geq 2}\sum_{r=2}^{n}\sum_{i=0}^{r-1}(-1)^{i}\binom{r-1}{i}\binom{n-i-1}{r-i-1}x^{r-1}y^{r}z^{n}\right)\\ &\qquad+\frac{1}{yz}\left(-\sum_{n\geq 2}yz^{n}-yz\right)\\ &=\frac{1}{yz}\left(A(x,y,z)-\sum_{n\geq 2}\sum_{r=2}^{n}\binom{n-r}{r-1}x^{r-1}y^{r}z^{n} -y\left(\frac{1}{1-z}-1-z\right)-yz\right)\tag{*}\\ &=\frac{1}{yz}\left(A(x,y,z)-\sum_{r\geq 1}\sum_{n\geq r+1}\binom{n-r-1}{r}x^{r}y^{r+1}z^{n} -y\left(\frac{1}{1-z}-1\right)\right)\\ &=\frac{1}{yz}\left(A(x,y,z)-y\sum_{r\geq 1}(xy)^r\sum_{n\geq 2}\binom{n-2}{r}z^{n+r-1} -y\left(\frac{1}{1-z}-1\right)\right)\\ &=\frac{1}{yz}\left(A(x,y,z)-yz\sum_{n\geq 0}z^n\sum_{r\geq 1}\binom{n}{r}(xyz)^r -y\left(\frac{1}{1-z}-1\right)\right)\\ &=\frac{1}{yz}\left(A(x,y,z)-yz\sum_{n\geq 0}z^n\left((1+xyz)^n-1\right) -y\left(\frac{1}{1-z}-1\right)\right)\\ &=\frac{1}{yz}\left(A(x,y,z)-yz\left(\frac{1}{1-(1+xyz)z}-\frac{1}{1-z}\right) -y\left(\frac{1}{1-z}-1\right)\right)\\ &=\frac{1}{yz}A(x,y,z)-\frac{1}{1-(1+xyz)z} \end{align*}
Note: In line $(*)$ we used the identity $\sum_{i=0}^{r-1}(-1)^{i}\binom{r-1}{i}\binom{n-i-1}{r-i-1}=\binom{n-r}{r-1}$ which can be shown e.g. by induction.
Putting all together gives an intermediate result for $A(x,y,z)$: \begin{align*} -A(x,y,z)&=\frac{1}{xyz}A(x,y,z)-\frac{1}{x}\left(\frac{1}{1-(1+y)z}\right)-\frac{1}{yz}A(x,y,z)\\ &+\frac{1}{1-(1+xyz)z}\\ -xyzA(x,y,z)&=A(x,y,z)-\frac{yz}{1-(1+y)z}-xA(x,y,z)\\ &+\frac{xyz}{1-(1+xyz)z}\\ A(x,y,z)(1-x+xyz)&=\frac{yz}{1-(1+y)z}-\frac{xyz}{1-(1+xyz)z}\\ A(x,y,z)&=\frac{yz}{1-x(1-yz)}\left(\frac{1}{1-(1+y)z}-\frac{x}{1-(1+xyz)z}\right) \end{align*}
Now we calculate $[z^n]A(x,y,z)$, the coefficient of $z^n$ from $A(x,y,z)$.
\begin{align*} [z^n]&\frac{yz}{1-x(1-yz)}\frac{1}{1-(1+y)z}\\ &=y[z^{n-1}]\sum_{t\geq 0}x^t(1-yz)^t\sum_{u\geq 0}(1+y)^{u}z^u\\ &=y[z^{n-1}]\sum_{t\geq 0}x^t\sum_{k=0}^{t}\binom{t}{k}(-yz)^k\sum_{u\geq 0}z^u\sum_{l=0}^{u}\binom{u}{l}y^l\\ &=y[z^{n-1}]\sum_{k\geq 0}(-yz)^k\sum_{t\geq k}\binom{t}{k}x^t\sum_{u\geq 0}z^u\sum_{l=0}^{u}\binom{u}{l}y^l\\ &=y[z^{n-1}]\sum_{k\geq 0}(-yz)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t+k}\sum_{u\geq 0}z^u\sum_{l=0}^{u}\binom{u}{l}y^l\\ &=y\sum_{k\geq 0}^{n-1}(-xy)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}[z^{n-1-k}]\sum_{u\geq 0}z^u\sum_{l=0}^{u}\binom{u}{l}y^l\\ &=y\sum_{k\geq 0}(-xy)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\sum_{l=0}^{n-1-k}\binom{n-1-k}{l}y^l \end{align*}
\begin{align*} [z^n]&\frac{yz}{1-x(1-yz)}\frac{x}{1-(1+xyz)z}\\ &=xy[z^{n-1}]\sum_{t\geq 0}x^t(1-yz)^t\sum_{u\geq 0}(1+xyz)^{u}z^u\\ &=xy[z^{n-1}]\sum_{t\geq 0}x^t\sum_{k=0}^{t}\binom{t}{k}(-yz)^k\sum_{u\geq 0}z^u\sum_{l=0}^{u}\binom{u}{l}(xyz)^l\\ &=xy[z^{n-1}]\sum_{k\geq 0}(-yz)^k\sum_{t\geq k}\binom{t}{k}x^t\sum_{l\geq 0}(xyz)^l\sum_{u\geq l}\binom{u}{l}z^u\\ &=xy[z^{n-1}]\sum_{k\geq 0}(-yz)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t+k}\sum_{l\geq 0}(xyz)^l\sum_{u\geq 0}\binom{u+l}{l}z^{u+l}\\ &=xy\sum_{k\geq 0}(-xy)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}[z^{n-1-k}]\sum_{l\geq 0}(xyz^2)^l\sum_{u\geq 0}\binom{u+l}{l}z^{u}\\ &=xy\sum_{k\geq 0}(-xy)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\sum_{l=0}^{n-1-k}(xy)^l[z^{n-1-k-2l}]\sum_{u\geq 0}\binom{u+l}{l}z^{u}\\ &=xy\sum_{k\geq 0}(-xy)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\sum_{l=0}^{n-1-k}\binom{n-1-k-l}{l}(xy)^l \end{align*}
Putting all together gives:
Now we calculate the coefficients of $y^{r}z^{n}$ from $A(x,y,z)$
\begin{align*} [y^rz^n]&A(x,y,z)=\\ &[y^{r-1}]\sum_{k\geq 0}(-xy)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\sum_{l=0}^{n-1-k}\binom{n-1-k}{l}y^l\\ &-[y^{r-1}]x\sum_{k\geq 0}(-xy)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\sum_{l=0}^{n-1-k}\binom{n-1-k-l}{l}(xy)^l\\ &=\sum_{k\geq 0}^{r-1}(-x)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}[y^{r-1-k}]\sum_{l=0}^{n-1-k}\binom{n-1-k}{l}y^l\\ &-x\sum_{k\geq 0}^{r-1}(-x)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}[y^{r-1-k}]\sum_{l=0}^{n-1-k}\binom{n-1-k-l}{l}(xy)^l\\ &=\sum_{k=0}^{r-1}(-x)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\binom{n-1-k}{r-1-k}\\ &-x\sum_{k=0}^{r-1}(-x)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\binom{n-r}{r-1-k}x^{r-1-k}\\ &=\sum_{k=0}^{r-1}\binom{n-1-k}{r-1-k}(-x)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\\ &-x^{r}\sum_{k=0}^{r-1}\binom{n-r}{r-1-k}(-1)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t} \end{align*}
Note: Observe that the second summand contains only terms with powers of $x$ greater than or equal to $r$. This means, that it does not contribute to the coefficients $a_{n,r,j}$ we are interested in. So, we can conclude that $A(x,y,z)$ simplifies to:
Finally:
For $0\leq j<r$ we get:
\begin{align*} [x^jy^rz^n]&A(x,y,z)\\ &=[x^j]\sum_{k=0}^{j}\binom{n-1-k}{r-1-k}(-x)^k\sum_{t\geq 0}\binom{t+k}{k}x^{t}\\ &=\sum_{k=0}^{j}\binom{n-1-k}{r-1-k}(-1)^k[x^{j-k}]\sum_{t\geq 0}\binom{t+k}{k}x^{t}\\ &=\sum_{k=0}^{j}(-1)^k\binom{j}{k}\binom{n-1-k}{r-1-k} \end{align*}
So, we have rediscovered the formula from above: