Saturday, 20 August 2016

combinatorics - Proving sumjt=1sumtr=1(1)r+tbinomj1t1binomt1r1f(r)=f(j)



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





Let jN and f:NR, then
jt=1tr=1(1)r+t(j1t1)(t1r1)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 (j1k1,k2,k3). So perhaps something like (f(j)1+1)j1, 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
jt=r(1)r+t(j1t1)(t1r1)=jt=r(1)r+t(j1t1)


It should be enough to show that this is 1 when j=r and 0 otherwise. First one is simple
rt=r(1)r+t(r1t1)=(1)2r(r1r1)=1
but how to show it is equal to 0 in other cases (jr) ...


Answer



We seek to verify that



nk=1kq=1(1)k+q(n1k1)(k1q1)f(q)=f(n).



Exchange sums to obtain



nq=1nk=q(1)k+q(n1k1)(k1q1)f(q)=nq=1f(q)nk=q(1)k+q(n1k1)(k1q1).



Now we get for the inner coefficient




(n1k1)(k1q1)=(n1)!(nk)!(q1)!(kq)!=(n1q1)(nqnk).



This yields for the sum



nq=1f(q)(n1q1)(1)qnk=q(nqnk)(1)k=nq=1f(q)(n1q1)nqk=0(nqnqk)(1)k=nq=1f(q)(n1q1)nqk=0(nqk)(1)k.



We get



nq=1f(q)(n1q1)[[nq=0]]=f(n)(n1n1)=f(n).


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...