Asymptotic behavior of sum of squares of combinatorial numbers with a weight. 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.
 A: 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) $$
A: 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.
