Sum Binomials: Proving Numerical Test Result

[Bibubo]

I have this sum $$\left(N+1\right)^{2}\underset{j=1}{\overset{N}{\sum}}\frac{\left(-1\right)^{j}}{2j+1}\dbinom{N}{j}\dbinom{N+j}{j-1}\underset{i=1}{\overset{N}{\sum}}\frac{\left(-1\right)^{i}}{\left(2i+1\right)\left(i+j\right)}\dbinom{N}{i}\dbinom{N+i}{i-1}$$ and numerical test indicates that is equal to $$\frac{\left(N+1\right)N}{\left(2N+1\right)^{2}}$$ but I'm not able to prove it. Thank you.

 

[Opalg]

I have this sum $$\left(N+1\right)^{2}\underset{j=1}{\overset{N}{\sum}}\frac{\left(-1\right)^{j}}{2j+1}\dbinom{N}{j}\dbinom{N+j}{j-1}\underset{i=1}{\overset{N}{\sum}}\frac{\left(-1\right)^{i}}{\left(2i+1\right)\left(i+j\right)}\dbinom{N}{i}\dbinom{N+i}{i-1}$$ and numerical test indicates that is equal to $$\frac{\left(N+1\right)N}{\left(2N+1\right)^{2}}$$ but I'm not able to prove it. Thank you.

I can't prove it either, but I have a framework where this result fits. If you write the sum as $$S_n = \sum_{i,j=1}^n \frac1{2i+1}\frac1{2j+1} \frac{(-1)^{i+j}(n+1)^2}{i+j}{n\choose i}{n+i\choose i-1} {n\choose j}{n+i\choose j-1}$$ and use the fact that $${n+i\choose i} = \frac{n+1}i{n+i\choose i-1}$$, you see that $$S_n = \sum_{i,j=1}^n \frac1{2i+1}\frac1{2j+1} \frac{(-1)^{i+j}ij}{i+j}{n\choose i}{n+i\choose i} {n\choose j}{n+i\choose j}.$$ That sum looks remarkably similar to those that occurred in http://mathhelpboards.com/linear-abstract-algebra-14/find-a_1-3-a_2-5-a-7056.html (see in particular the equations labelled (1) and (2) in my comment #4 there). Using the notation of that thread, let $H_n$ be the $n\times n$ Hilbert matrix, let $H_n^{-1} = X_n^*X_n$ be the factorisation of its inverse into lower- and upper-triangular matrices, and let $k$ be the vector $\bigl(\frac13,\frac15,\ldots, \frac1{2n+1}\bigr).$ Then your sum $S_n$ is exactly one-quarter of the sum in that other thread, namely $S_n = \langle H_n^{-1}k,k\rangle = \|X_nk\|^2$. In that thread, anemone and I decided that this must be equal to $\frac14\!\bigl(1-\frac1{(2n+1)^2}\bigr)$, which agrees with your conjecture $S_n = \frac{n(n+1)}{(2n+1)^2}.$ But I still can't prove it!

 

[Bibubo]

I can't prove it either, but I have a framework where this result fits. If you write the sum as $$S_n = \sum_{i,j=1}^n \frac1{2i+1}\frac1{2j+1} \frac{(-1)^{i+j}(n+1)^2}{i+j}{n\choose i}{n+i\choose i-1} {n\choose j}{n+i\choose j-1}$$ and use the fact that $${n+i\choose i} = \frac{n+1}i{n+i\choose i-1}$$, you see that $$S_n = \sum_{i,j=1}^n \frac1{2i+1}\frac1{2j+1} \frac{(-1)^{i+j}ij}{i+j}{n\choose i}{n+i\choose i} {n\choose j}{n+i\choose j}.$$ That sum looks remarkably similar to those that occurred in http://mathhelpboards.com/linear-abstract-algebra-14/find-a_1-3-a_2-5-a-7056.html (see in particular the equations labelled (1) and (2) in my comment #4 there). Using the notation of that thread, let $H_n$ be the $n\times n$ Hilbert matrix, let $H_n^{-1} = X_n^*X_n$ be the factorisation of its inverse into lower- and upper-triangular matrices, and let $k$ be the vector $\bigl(\frac13,\frac15,\ldots, \frac1{2n+1}\bigr).$ Then your sum $S_n$ is exactly one-quarter of the sum in that other thread, namely $S_n = \langle H_n^{-1}k,k\rangle = \|X_nk\|^2$. In that thread, anemone and I decided that this must be equal to $\frac14\!\bigl(1-\frac1{(2n+1)^2}\bigr)$, which agrees with your conjecture $S_n = \frac{n(n+1)}{(2n+1)^2}.$ But I still can't prove it!

Yes I see what you say... I've think to use in some way the Legendre shifted polynomials $$P_{N}\left(x\right)=\left(-1\right)^{N}\underset{i=0}{\overset{N}{\sum}}\dbinom{N}{i}\dbinom{N+i}{i}\left(-x\right)^{i}$$ because the sums are very similar, and because we have $$\int_{0}^{1}P_{m}\left(x\right)P_{n}\left(x\right)dx=\frac{\delta_{m,n}}{2n+1}$$ where $\delta_{m,n}$ is the Kronecker delta. Is it a stupid idea?

 

[Opalg]

I've think to use in some way the Legendre shifted polynomials $$P_{N}\left(x\right)=\left(-1\right)^{N}\underset{i=0}{\overset{N}{\sum}}\dbinom{N}{i}\dbinom{N+i}{i}\left(-x\right)^{i}$$

The comment about shifted Legendre polynomials prompted me to think about this problem again. In the http://mathhelpboards.com/linear-abstract-algebra-14/find-a_1-3-a_2-5-a-7056.html#post32971, I showed how to reduce the problem to proving the identity $$\sum_{k=1}^n \frac{(-1)^kk}{(n+k)(2k+1)}{n\choose k}{n+k\choose k} = \frac{-1}{4n^2-1} \qquad(*)$$ (see equation (4) and the following sentence in that thread). I posted this identity in the MathOverflow forum, where it received an amazingly clever proof that I can't resist repeating here.

The trick is to write the expression $\dfrac{(-1)^n(x-2)(x-4)\cdots(x- (2n-2))}{(x+2)(x+4)\cdots(x+2n)}$ as a sum of partial fractions. If you use the cover-up rule to find the coefficient of $\dfrac1{x+2k}$, you find that it is equal to $$ \frac{(-1)^n(-2k-2)(-2k-4) \cdots(-2k-2n+2)} {\bigl((-2k+2)(-2k+4)\cdots(-2)\bigr) \bigl(2\cdot4\cdots(-2k+2n)\bigr)}.$$ There are $n-1$ factors in the numerator, each of them a multiple of $-2$. In the denominator there are $k-1$ factors that are multiples of $-2$; and $n-k$ positive factors that are multiples of $2$. after cancelling all these $-1$s and $2$s, the coefficient of $\dfrac1{x+2k}$ becomes $$\begin{aligned}\frac{(-1)^k(k+1)(k+2)\cdots(n+k-1)}{(k-1)!(n-k)!} &= \frac{(-1)^k(n+k-1)!}{k!(k-1)!(n-k)!} \\ &= \frac{(-1)^kk}{n+k}\frac{(n+k)!n!}{(k!)^2((n-k)!n!} = \frac{(-1)^kk}{(n+k)}{n\choose k}{n+k\choose k}.\end{aligned}$$ Thus the partial fraction decomposition is $$ \sum_{k=1}^n \frac{(-1)^kk}{(n+k)(x+2k)}{n\choose k}{n+k\choose k} = \dfrac{(-1)^n(x-2)(x-4)\cdots(x- (2n-2))}{(x+2)(x+4)\cdots(x+2n)}.$$ Now put $x=1$. The left side then becomes the left side of (*). The right side becomes $$-\dfrac{1\cdot3 \cdot5\cdots(2n-3)}{3\cdot5 \cdot7\cdots(2n+1)} = \dfrac{-1}{(2n-1)(2n+1)} = \dfrac{-1}{4n^2-1},$$ just as we wanted!

 

[Bibubo]

The comment about shifted Legendre polynomials prompted me to think about this problem again. In the http://mathhelpboards.com/linear-abstract-algebra-14/find-a_1-3-a_2-5-a-7056.html#post32971, I showed how to reduce the problem to proving the identity $$\sum_{k=1}^n \frac{(-1)^kk}{(n+k)(2k+1)}{n\choose k}{n+k\choose k} = \frac{-1}{4n^2-1} \qquad(*)$$ (see equation (4) and the following sentence in that thread). I posted this identity in the MathOverflow forum, where it received an amazingly clever proof that I can't resist repeating here.

The trick is to write the expression $\dfrac{(-1)^n(x-2)(x-4)\cdots(x- (2n-2))}{(x+2)(x+4)\cdots(x+2n)}$ as a sum of partial fractions. If you use the cover-up rule to find the coefficient of $\dfrac1{x+2k}$, you find that it is equal to $$ \frac{(-1)^n(-2k-2)(-2k-4) \cdots(-2k-2n+2)} {\bigl((-2k+2)(-2k+4)\cdots(-2)\bigr) \bigl(2\cdot4\cdots(-2k+2n)\bigr)}.$$ There are $n-1$ factors in the numerator, each of them a multiple of $-2$. In the denominator there are $k-1$ factors that are multiples of $-2$; and $n-k$ positive factors that are multiples of $2$. after cancelling all these $-1$s and $2$s, the coefficient of $\dfrac1{x+2k}$ becomes $$\begin{aligned}\frac{(-1)^k(k+1)(k+2)\cdots(n+k-1)}{(k-1)!(n-k)!} &= \frac{(-1)^k(n+k-1)!}{k!(k-1)!(n-k)!} \\ &= \frac{(-1)^kk}{n+k}\frac{(n+k)!n!}{(k!)^2((n-k)!n!} = \frac{(-1)^kk}{(n+k)(2k+1)}{n\choose k}{n+k\choose k}.\end{aligned}$$ Thus the partial fraction decomposition is $$ \sum_{k=1}^n \frac{(-1)^kk}{(n+k)(2k+1)(x+2k)}{n\choose k}{n+k\choose k} = \dfrac{(-1)^n(x-2)(x-4)\cdots(x- (2n-2))}{(x+2)(x+4)\cdots(x+2n)}.$$ Now put $x=1$. The left side then becomes the left side of (*). The right side becomes $\dfrac{-(2n-3)!}{(2n+1)!} = \dfrac{-1}{(2n-1)(2n+1)} = \dfrac{-1}{4n^2-1}$, just as we wanted!

Grat job! I have only one question... if you put $x=1$ in your identity you obtain $$\underset{k=1}{\overset{n}{\sum}}\frac{\left(-1\right)^{k}k}{\left(n+k\right)\left(2k+1\right)\left(1+2k\right)}\,\dbinom{n}{k}\dbinom{n+k}{k}$$ and it isn't like the left side of (*) because there is a another factor $1+2k$... where am I wrong? Thank you!

 

[Opalg]

Grat job! I have only one question... if you put $x=1$ in your identity you obtain $$\underset{k=1}{\overset{n}{\sum}}\frac{\left(-1\right)^{k}k}{\left(n+k\right)\left(2k+1\right)\left(1+2k\right)}\,\dbinom{n}{k}\dbinom{n+k}{k}$$ and it isn't like the left side of (*) because there is a another factor $1+2k$... where am I wrong? Thank you!

It's not you that is wrong, it was me. I accidentally put an extraneous $2k+1$ into the previous line. I have now edited it out.

Edit. I have also corrected another mistake. In the last line, the numerator and denominator of the fraction should not have consisted of factorials, but of products of odd numbers.