2

I am, through some combinatorial problems which I'm working on, trying to figure out what the following sum becomes as $n\rightarrow \infty$:

\begin{equation*} \sum_{i=1}^{n-1} \binom{n}{i}3^{\binom{n-i}{2}-\binom{n}{2}}2^{\binom{i}{2}} \end{equation*}

The main question is: Does it go to infinity, $0$ or something else? Can we at least exclude some of the cases (like it going to 0)?

zoli
  • 20,452
Ove Ahlman
  • 4,329

1 Answers1

1

First note that $${n-i \choose 2}-{n \choose 2} = \frac{(n-i)(n-i-1)-n(n-1)}{2}=\frac{-2in+i^2+i}{2}$$

Thus \begin{align} 3^{{n-i \choose 2}-{n \choose 2}}2^{{i \choose 2}} &= 3^{\frac{-2in+i^2+i}{2}}2^{\frac{i(i-1)}{2}} \\ &= 3^{-in} \cdot 3^{\frac{i^2+i}{2}} \cdot 2^{\frac{i(i-1)}{2}} \\ &< 3^{-in} \cdot 6^{\frac{i^2+i}{2}} \\ &< 3^{-in} \cdot 6^{\frac{in}{2}} \\ &= \left(0.5\right)^{-in} \\ &< n^{-i} \end{align}

Since $(n+\frac{1}{n})^n = \sum n^{-i} {n \choose i}$ goes to $e$, we have that the given sum is smaller than or equal to Euler's number.

wythagoras
  • 25,026
  • Altough there are some errors and overapproximations in your calculations, they helped me to the right direction. Thank you. – Ove Ahlman May 07 '15 at 13:25
  • Would you be so kind to point out these errors? I can learn of that too. – wythagoras May 07 '15 at 13:31
  • $3^{-in} \cdot 3^{(i^2+i)/2} \cdot 2^{i(i-1)} < 3^{-in/2}2^{in/2} = (\sqrt{2/3})^{in}$. Approximating this to $n^-i$ is nice, however this is a large step, and it is even nicer thus to approximate it to $n^{-i-1}$ as this means we get (\frac{1}{n} (1 + \frac{1}{n})^n) which goes to 0, – Ove Ahlman May 08 '15 at 04:53
  • Indeed, that is true. Thank you. – wythagoras May 08 '15 at 06:32