Upper bound of $\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}$

Question

I would like to find max (or sup.) of the sum: $$S=\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}.$$ I found $S\le \frac{1}{\sqrt{\pi n}}.2(n+1).4^n$ but It seems it's not correct. (I used this formular :$\sum\limits_{i=1}^{j-1}{n \choose i}\le 2j {n \choose j-1}$, is it true?)

Answer 1

Using the decomposition $${n+1\choose j}={n\choose j}+{n\choose j-1},$$ and the change of variable $j\to j-1$ in the second sum that this decomposition yields, one gets $$S=\sum_{i\lt j}{n+1\choose j}{n\choose i}=\sum_{i\lt j}{n\choose j}{n\choose i}+\sum_{i\leqslant j}{n\choose j}{n\choose i}.$$ By symmetry, the last sum on the RHS is $$\sum_{i\leqslant j}{n\choose j}{n\choose i}=\sum_{i\geqslant j}{n\choose j}{n\choose i},$$ hence $$S=\sum_{i,j}{n\choose j}{n\choose i}=\left(\sum_{i}{n\choose i}\right)^2=4^n.$$