"Concrete Mathematics" second edition equation (5.32)

$\sum_{j,k} (-1)^{j+k} \binom{j+k}{k+l} \binom{r}{j} \binom{n}{k} \binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l} \binom{s-r}{m-n-l}$

What is the error in the following proof?

left

$=\sum_{j,k} (-1)^{j+k} \sum_{i} \binom{j}{k+l-i} \binom{k}{i} \binom{r}{j} \binom{n}{k} \binom{s+n-j-k}{m-j}$ applying (5.22) $r=j,s=k,m=0,n=k+l$

$=\sum_{j,k} (-1)^{j+k} \sum_{i} \binom{r}{j} \binom{j}{i} \binom{n}{k} \binom{k}{i-l} \binom{s-n-j-k}{m-j}$ applying (5.21) $r=r,m=j,i=k;r=n,m=k,k=i-l$

$=\sum_{j,k} (-1)^{j+k} \sum_{i} \binom{r-i}{j-i} \binom{n+l-i}{k+l-i} \binom{s+n-j-k}{m-j}$

$=\sum_{j,k} (-1)^{j+k} \sum_{i} \binom{r-i}{j-i} \binom{n+l-i}{k+l-i} \binom{s+n-j-k}{s+n-m-k}$

$=\sum_{i} (-1)^i \sum_{k} (-1)^k \binom{n+l-i}{k+l-i} \sum_{j} (-1)^{j-i} \binom{s+n-k-j}{s+n-k-m} \binom{r-i}{j-i}$ applying "The Art of Computer Programming" volume 1, 3rd Edition, 1.2.6 (24): $r=s+n-k,s=r-i,m=s+n+k-m,t=i,k=j$

$=\sum_{i} (-1)^i \sum_{k} (-1)^k \binom{n+l-i}{k+l-i} \binom{s+n-k-i-r+i}{s+n-k-i-s-n+k+m}$

$=\sum_{i} (-1)^i \sum_{k} (-1)^k \binom{n+l-i}{k+l-i} \binom{s+n-k-r}{m-i}$

$=\sum_{i} (-1)^i \sum_{k} (-1)^{k-(i-l)} \binom{s+n-k-r}{m-i} \binom{n-(i-l)}{k-(i-l)} (-1)^{i-l}$ applying "The Art of Computer Programming" volume 1, 3rd Edition, 1.2.6 (24): $r=s+n-r,s=n-(i-l),m=m-i,t=i-l$

$=\sum_{i} (-1)^{i} \binom{s+n-r-i+l-n+i-l}{s+n-r-i+l-m+i} (-1)^{i-l}$

$=\sum_{i} (-1)^{l} \binom{s-r}{s-r+l+n-m}$

$\sum_{j,k} (-1)^{j+k} \binom{j+k}{k+l} \binom{r}{j} \binom{n}{k} \binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l} \binom{s-r}{m-n-l}$

What is the error in the following proof?

left

$=\sum_{j,k} (-1)^{j+k} \sum_{i} \binom{j}{k+l-i} \binom{k}{i} \binom{r}{j} \binom{n}{k} \binom{s+n-j-k}{m-j}$ applying (5.22) $r=j,s=k,m=0,n=k+l$

$=\sum_{j,k} (-1)^{j+k} \sum_{i} \binom{r}{j} \binom{j}{i} \binom{n}{k} \binom{k}{i-l} \binom{s-n-j-k}{m-j}$ applying (5.21) $r=r,m=j,i=k;r=n,m=k,k=i-l$

$=\sum_{j,k} (-1)^{j+k} \sum_{i} \binom{r-i}{j-i} \binom{n+l-i}{k+l-i} \binom{s+n-j-k}{m-j}$

$=\sum_{j,k} (-1)^{j+k} \sum_{i} \binom{r-i}{j-i} \binom{n+l-i}{k+l-i} \binom{s+n-j-k}{s+n-m-k}$

$=\sum_{i} (-1)^i \sum_{k} (-1)^k \binom{n+l-i}{k+l-i} \sum_{j} (-1)^{j-i} \binom{s+n-k-j}{s+n-k-m} \binom{r-i}{j-i}$ applying "The Art of Computer Programming" volume 1, 3rd Edition, 1.2.6 (24): $r=s+n-k,s=r-i,m=s+n+k-m,t=i,k=j$

$=\sum_{i} (-1)^i \sum_{k} (-1)^k \binom{n+l-i}{k+l-i} \binom{s+n-k-i-r+i}{s+n-k-i-s-n+k+m}$

$=\sum_{i} (-1)^i \sum_{k} (-1)^k \binom{n+l-i}{k+l-i} \binom{s+n-k-r}{m-i}$

$=\sum_{i} (-1)^i \sum_{k} (-1)^{k-(i-l)} \binom{s+n-k-r}{m-i} \binom{n-(i-l)}{k-(i-l)} (-1)^{i-l}$ applying "The Art of Computer Programming" volume 1, 3rd Edition, 1.2.6 (24): $r=s+n-r,s=n-(i-l),m=m-i,t=i-l$

$=\sum_{i} (-1)^{i} \binom{s+n-r-i+l-n+i-l}{s+n-r-i+l-m+i} (-1)^{i-l}$

$=\sum_{i} (-1)^{l} \binom{s-r}{s-r+l+n-m}$

Last edited: