My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
August 9th, 2016, 12:30 AM   #1
Newbie
 
Joined: Nov 2013

Posts: 14
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.
rubis is offline  
 
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
combinatorial, equation, error, identical, proof



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fermat proof, where is the error ? complicatemodulus Number Theory 19 December 16th, 2014 09:27 AM
Another proof tht 0=1. Please spot the error STxAxTIC Number Theory 38 December 9th, 2013 11:28 PM
Combinatorial proof other than strong induction mahjk17 Applied Math 5 May 30th, 2012 10:25 PM
Combinatorial proof help please! erogol Applied Math 1 March 5th, 2009 08:31 AM
Combinatorial proof help please! erogol Applied Math 1 March 3rd, 2009 02:46 PM





Copyright © 2017 My Math Forum. All rights reserved.