My Math Forum Error in proof of combinatorial identical equation

 Applied Math Applied Math Forum

 August 9th, 2016, 12:30 AM #1 Newbie   Joined: Nov 2013 Posts: 16 Thanks: 0 Error in proof of combinatorial identical equation "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}$ Last edited by rubis; August 9th, 2016 at 12:35 AM.

 Tags combinatorial, equation, error, identical, proof

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post complicatemodulus Number Theory 19 December 16th, 2014 09:27 AM STxAxTIC Number Theory 38 December 9th, 2013 11:28 PM mahjk17 Applied Math 5 May 30th, 2012 10:25 PM erogol Applied Math 1 March 5th, 2009 08:31 AM erogol Applied Math 1 March 3rd, 2009 02:46 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top