Suppose we have two lists $a=a_{1},a_{2},\ldots,a_{n}$, $\ \ b=b_{1},b_{2},\ldots,b_{n}$ and we want to determine how many ways there are to insert $k$ identical elements $X$ independently into both lists (i.e. at the beginning, between two elements, or at the end, where we can have consecutive Xs) and $k$ can range from 1 to $n$.
Given $k$, we can model this as choosing $k$ slots with replacement out of the $n+1$ available slots. Since both lists are independent, this should be squared, giving $$\binom{n+k}{n}^{2}$$
Considering any possible $k\in\left[n\right]$, this becomes $$\sum_{k=1}^{n}\binom{n+k}{n}^{2}$$
Is this analysis correct? If so, what is the best exponential lower bound I can get for the above expression?