Asymptotic behavior of sum of squares of combinatorial numbers with a weight.

Question

Consider the following sequence of natural numbers,

$$M_n = \sum_{k=0}^n \binom{n}{k}^2 4^k$$

We can interpret $M_n$ as the cardinality of the set $X$ of $(2\times n)$-matrices with entries in $\{-1,0,1\}$ which have the same number of zeroes in both rows. My question is about the asymptotic behaviour of this sequence. It must be of the form

$$M_n \sim C \frac{9^n}{\sqrt{\pi n}}$$

but I am unable to compute the constant $C$.

What I am able to get is that $\sqrt{2}/2 \leq C \leq 3/2$. I briefly comment how I get these bounds.

• Lower bound: From all the $2\times n$ matrices which have exactly $2p$ rows of the form $\binom{\pm 1}{0}$ or $\binom{0}{\pm 1}$, only those which have exactly $p$ rows from each of the two types are in the set $X$. The proportion is thus $\binom{2p}{p}/{2^{2p}}$ . There are essentially $9^n/2$ matrices with entries $\{-1,0,1\}$ and even number of $\binom{\pm 1}{0}$ or $\binom{0}{\pm 1}$ entires, so we can write $$M_n > \min_{2p\leq n}\left\{\binom{2p}{p}2^{-2p}\right\} \cdot 9^n/2$$ The sequence to minimize is decreasing, so (assume $n$ is even for simplicity) $$M_n > \binom{2n}{n}2^{-2n} \cdot 9^n/2$$ and applying Stirling's formula we get the lower bound.

• Upper bound: If we fix a lower row $F$ with $p$ many zeros, there $k_p = 2^{n-p} \binom{n}{p}$ matrices in whose lower row is F. Since there are $3^n$ possible rows, we can bound, $$M_n < 3^n \max_{p\leq n}k_p$$ This maximum can be computed by looking at the quotient $k_{p+1}/k_p$ and one checks that it is attained essentially at $p = n/3$, so $$M_n < 3^n \cdot 2^{2n/3}\binom{n}{n/3}$$ and applying again Stirling's formula we get the upper bound.

Answer 1

A probabilistic approach: Consider the experiment of throwing the values $\{-1,0,1\}$ with uniform probability on a $2\times n$ matrix. Let $n_1,n_2$ be the number of zeroes in each row, let $d=n_1-n_2$ and $P_n=P(d=0)$. Then

$$P_n = \frac{M_n}{3^{2n}}$$

Now, for large $n$, $n_1$ approaches a normal $N(\frac{1}{3}n,\frac{2}{9}n)$, so $d$ approaches a normal $N(0,\frac{4}{9}n)$. The probability that the discrete variable $d$ is zero can then be approximated by

$$P_n \approx \frac{1}{\sqrt{2 \pi \sigma_d^2}}= \frac{3}{2 \sqrt{2 \pi n}}$$

Hence

$$ M_n \approx \frac{3}{2} \frac{9^n}{\sqrt{ 2 \pi n}} =\frac{3}{\sqrt{8}} \frac{9^n}{\sqrt{\pi n}}$$

This approximation can be made rigorous, and refined to get more terms, via Edgeworth expansion; see eg here. Unless I've messed something:

$$ M_n = \frac{3}{2} \frac{9^n}{\sqrt{2 \pi \, n}}\left( 1 - \frac{3}{32} n^{-1} + O(n^{-2})\right) $$

Answer 2

Another approach to your problem is to notice that, your sum can have the following closed form in terms of the Legendre polynomials

$$ M_n = \sum_{k=0}^n \binom{n}{k}^2 4^k=\left( -3 \right)^{n}P_n\left(-\frac{5}{3} \right)=(-3)^n(-1)^nP_n\left( \frac{5}{3}\right)=3^n P_n\left( \frac{5}{3}\right)\longrightarrow(1).$$

Added:

The last equality in $(1)$ follows from the property $P_n(-x)=(-1)^nP_n(x)$ of Legendre polynomials. Appealing to the formula of Laplace-Heine

$$ P_n(x) \sim \frac{1}{\sqrt{2\pi n}}\frac{\left(x+(x^2-1)^{\frac{1}{2}}\right)^{n+\frac{1}{2}}}{(x^2-1)^{\frac{1}{4}}},$$

our sum will have the asymptotic formula

$$ M_n = 3^n P_n\left( \frac{5}{3}\right) \sim \frac{3\sqrt{2}}{4}\,{\frac {{9}^{n}}{\sqrt {\pi n}}}. $$

Now, the wanted $C$ follows.