Proving $\sum_{t=1}^j \sum_{r=1}^{t} (-1)^{r+t} \binom{j-1}{t-1} \binom{t-1}{r-1} f(r) = f(j)$

Question

I've run into the following identity and trying to prove it:

Let $j \in \mathbb{N}$ and $f:\mathbb{N} \to \mathbb{R}$, then $$ \sum_{t=1}^j \sum_{r=1}^{t} (-1)^{r+t} \binom{j-1}{t-1} \binom{t-1}{r-1} f(r) = f(j) $$

I've so far tried to find some connection with the multinomial theorem, since the product of the two binomials in the expression is just multinomial $\binom{j-1}{k1,k2,k3}$. So perhaps something like $(f(j)-1+1)^{j-1}$, but it does not quite fit. I am missing something, any ideas how to proceed?

Edit: Further attempt, trying to collect "coefficients" of $f(r)$ yields $$ \sum_{t=r}^j(-1)^{r+t}\binom{j-1}{t-1}\binom{t-1}{r-1} = \sum_{t=r}^j (-1)^{r+t}\binom{j-1}{t-1} $$ It should be enough to show that this is $1$ when $j=r$ and $0$ otherwise. First one is simple $$ \sum_{t=r}^r (-1)^{r+t}\binom{r-1}{t-1} = (-1)^{2r} \binom{r-1}{r-1} = 1 $$ but how to show it is equal to $0$ in other cases ($j\neq r $) ...

Answer 1

We seek to verify that

$$\sum_{k=1}^n \sum_{q=1}^k (-1)^{k+q} {n-1\choose k-1} {k-1\choose q-1} f(q) = f(n).$$

Exchange sums to obtain

$$\sum_{q=1}^n \sum_{k=q}^n (-1)^{k+q} {n-1\choose k-1} {k-1\choose q-1} f(q) \\ = \sum_{q=1}^n f(q) \sum_{k=q}^n (-1)^{k+q} {n-1\choose k-1} {k-1\choose q-1}.$$

Now we get for the inner coefficient

$${n-1\choose k-1} {k-1\choose q-1} = \frac{(n-1)!}{(n-k)! (q-1)! (k-q)!} = {n-1\choose q-1} {n-q\choose n-k}.$$

This yields for the sum

$$\sum_{q=1}^n f(q) {n-1\choose q-1} (-1)^q \sum_{k=q}^n {n-q\choose n-k} (-1)^k \\ = \sum_{q=1}^n f(q) {n-1\choose q-1} \sum_{k=0}^{n-q} {n-q\choose n-q-k} (-1)^k \\ = \sum_{q=1}^n f(q) {n-1\choose q-1} \sum_{k=0}^{n-q} {n-q\choose k} (-1)^k.$$

We get

$$\sum_{q=1}^n f(q) {n-1\choose q-1} [[n-q = 0]] = f(n) {n-1\choose n-1} = f(n).$$

Answer 2

Note that it is: $$ \begin{gathered} f(n) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)g(k)} \quad \Leftrightarrow \quad g(n) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^{\,n - k} \left( \begin{gathered} n \\ k \\ \end{gathered} \right)f(k)} \hfill \\ f(n) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} n \\ k \\ \end{gathered} \right)g(k)} \quad \Leftrightarrow \quad g(n) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \begin{gathered} n \\ k \\ \end{gathered} \right)f(k)} \hfill \\ \end{gathered} $$ because $$ \begin{gathered} f(n) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)g(k)} = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( { - 1} \right)^{\,k - j} \left( \begin{gathered} k \\ j \\ \end{gathered} \right)f(j)} } = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,n} \right)} {\left( {\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^{\,k - j} \left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( \begin{gathered} k \\ j \\ \end{gathered} \right)} } \right)f(j)} = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ j \\ \end{gathered} \right)\left( {\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^{\,k - j} \left( \begin{gathered} n - j \\ k - j \\ \end{gathered} \right)} } \right)f(j)} = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ j \\ \end{gathered} \right)\left( {\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n - j \\ k - j \\ \end{gathered} \right)1^{\,n - j - \left( {k - j} \right)} \left( { - 1} \right)^{\,k - j} } } \right)f(j)} = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ j \\ \end{gathered} \right)0^{\,n - j} f(j)} = f(n) \hfill \\ \end{gathered} $$ where from 2nd to 3rd line we apply the known trinomial revision.

In your case we have $$ \begin{gathered} f(j) = \sum\limits_{\left( {1\, \leqslant } \right)\,t\,\left( { \leqslant \,j} \right)} {\sum\limits_{\left( {1\, \leqslant } \right)\,r\,\left( { \leqslant \,t} \right)} {\left( { - 1} \right)^{\,r + t} \left( \begin{gathered} j - 1 \\ t - 1 \\ \end{gathered} \right)\left( \begin{gathered} t - 1 \\ r - 1 \\ \end{gathered} \right)f(r)} } = \hfill \\ = \sum\limits_{\left( {1\, \leqslant } \right)\,t\,\left( { \leqslant \,j} \right)} {\sum\limits_{\left( {1\, \leqslant } \right)\,r\,\left( { \leqslant \,t} \right)} {\left( { - 1} \right)^{\,r - t} \left( \begin{gathered} j - 1 \\ t - 1 \\ \end{gathered} \right)\left( \begin{gathered} t - 1 \\ r - 1 \\ \end{gathered} \right)f(r)} } = \hfill \\ = \sum\limits_{\left( {1\, \leqslant } \right)\,t\,\left( { \leqslant \,j} \right)} {\sum\limits_{\left( {1\, \leqslant } \right)\,r\,\left( { \leqslant \,t} \right)} {\left( { - 1} \right)^{\,r - 1 - \left( {t - 1} \right)} \left( \begin{gathered} j - 1 \\ t - 1 \\ \end{gathered} \right)\left( \begin{gathered} t - 1 \\ r - 1 \\ \end{gathered} \right)f(r)} } = \hfill \\ = \sum\limits_{\left( {1\, \leqslant } \right)\,t\,\left( { \leqslant \,j} \right)} {\sum\limits_{\left( {1\, \leqslant } \right)\,r\,\left( { \leqslant \,t} \right)} {\left( { - 1} \right)^{\,r - 1 - \left( {t - 1} \right)} \left( \begin{gathered} j - 1 \\ t - 1 \\ \end{gathered} \right)\left( \begin{gathered} t - 1 \\ r - 1 \\ \end{gathered} \right)g(r - 1)} } = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,t - 1\,\left( { \leqslant \,j - 1} \right)} {\sum\limits_{\left( {0\, \leqslant } \right)\,r - 1\,\left( { \leqslant \,t - 1} \right)} {\left( { - 1} \right)^{\,r - 1 - \left( {t - 1} \right)} \left( \begin{gathered} j - 1 \\ t - 1 \\ \end{gathered} \right)\left( \begin{gathered} t - 1 \\ r - 1 \\ \end{gathered} \right)g(r - 1)} } = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,j - 1} \right)} {\sum\limits_{\left( {0\, \leqslant } \right)\,l\,\left( { \leqslant \,k} \right)} {\left( { - 1} \right)^{\,l - k} \left( \begin{gathered} j - 1 \\ k \\ \end{gathered} \right)\left( \begin{gathered} k \\ l \\ \end{gathered} \right)g(l)} } = \hfill \\ = g(j - 1) = f(j) \hfill \\ \end{gathered} $$

Answer 3

$$ \begin{align} &\sum_{t=1}^j\sum_{r=1}^t(-1)^{r+t}\binom{j-1}{t-1}\binom{t-1}{r-1}\,f(r)\\[3pt] &=\sum_{r=1}^j\underbrace{\sum_{t=r}^j(-1)^{t-r}\binom{j-1}{r-1}\binom{j-r}{t-r}}\,\,f(r)\tag{1}\\ &=\sum_{r=1}^j\hspace{14mm}\underbrace{0^{\,j-r}\binom{j-1}{r-1}}_{[\,r=j\,]}\hspace{14mm}f(r)\tag{2}\\ &=f(j)\tag{3} \end{align} $$ Explanation:
$(1)$: change order of summation and apply $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c}$
$(2)$: $\sum\limits_{t=r}^j(-1)^{t-r}\binom{j-r}{t-r}=\sum\limits_{t=r}^j\binom{j-r}{t-r}1^{j-t}(-1)^{t-r}=(1-1)^{j-r}$
$(3)$: the only non-zero term is $r=j$ and that term is $f(j)$