Binomial identity arising from Catalan recurrence. The following identity features right at the end of the answer to another question I asked: https://math.stackexchange.com/a/4019598/155881.
$$F(x) = \frac{1}{\sqrt{1-4x}} \left(\frac{1- \sqrt{1-4x}}{2x}\right)^n = \sum\limits_{k=0}^{\infty}{n+2k \choose k}x^k$$
Haven't been able to prove this. We know the expansions of both terms on the left side, making the identity:
$$\left(\sum\limits_{j=0}^{\infty} \left(\binom{n+2j-1}{j} - \binom{n+2j-1}{j-1}\right)x^j\right)
\left(\sum\limits_{l=0}^{\infty}{2l \choose l} x^l\right) = \sum\limits_{k=0}^{\infty}{2n+k \choose k}x^k$$

My attempt:
An obvious thing to do is to try a convolution of the left side and equate coefficients of $x^k$ (also using an alternate expression for the first summation in the product of the left side):
$$\sum\limits_{l=0}^k {n+2l-1\choose l}\frac{l}{n+l} {2k-2l\choose k-l} = {2n+k\choose k}$$
Not sure how to make progress on this. Expanding the binomial terms doesn't lead anywhere.
 A: We seek to show that with
$$Q(z) = \frac{1}{\sqrt{1-4z}}
\left(\frac{1-\sqrt{1-4z}}{2z}\right)^n$$
we have
$$[z^k] Q(z) = {n+2k\choose k}.$$
Now with the branch cut on $[1/4, \infty)$ for $\sqrt{1-4z}$ we have
analyticity of $Q(z)$ in a neighborhood of the origin (note that the
exponentiated term does not in fact have a pole at $z=0$) and the Cauchy
Coefficient Formula applies. We obtain
$$[z^k] Q(z) = \frac{1}{2\pi i}
\int_{|z|=\varepsilon} \frac{1}{z^{k+1}}
\frac{1}{\sqrt{1-4z}}
\left(\frac{1-\sqrt{1-4z}}{2z}\right)^n \; dz.$$
We put $\sqrt{1-4z} = w$ so that  $\frac{1}{\sqrt{1-4z}} \; dz =
-\frac{1}{2} \; dw$  and $z=(1-w^2)/4.$ With $w = 1 - 2z - \cdots$ we get
as the image of $|z|=\varepsilon$ a contour that winds around $w=1$
counterclockwise once and may be  deformed to a circle, so that we obtain
$$[z^k] Q(z) =
-\frac{1}{2}
\frac{1}{2\pi i}
\int_{|w-1|=\gamma}
\frac{4^{k+1}}{(1-w^2)^{k+1}}
(1-w)^n
\frac{1}{2^n} \frac{4^n}{(1-w^2)^n}
\; dw
\\ = \frac{(-1)^k \times 2^{n+2k+1}}{2\pi i}
\int_{|w-1|=\gamma}
\frac{(w-1)^n}{(w^2-1)^{n+k+1}} \; dw
\\ = \frac{(-1)^k \times 2^{n+2k+1}}{2\pi i}
\int_{|w-1|=\gamma}
\frac{1}{(w-1)^{k+1}} \frac{1}{(w+1)^{n+k+1}} \; dw
\\ = \frac{(-1)^k \times 2^{k}}{2\pi i}
\int_{|w-1|=\gamma}
\frac{1}{(w-1)^{k+1}} \frac{1}{(1+(w-1)/2)^{n+k+1}} \; dw$$
Apply the Cauchy Residue Theorem to get
$$(-1)^k \times 2^k \times (-1)^k \frac{1}{2^k}
{n+k+k\choose n+k} = \bbox[5px,border:2px solid #00A000]{
{n+2k\choose k}}$$
as claimed.
A: Define $$ F_n(x):=\sum_{k=0}^\infty c_{n,k}x^k \tag{1} $$ where
$$  c_{n,k}:={n+2k \choose k}. \tag{2}  $$
Verify the binomial identity
$$ c_{n+1,k-1}=c_{n,k}-c_{n-1,k}. \tag{3} $$
Define $$ b:=\frac{1-\sqrt{1-4x}}{2x}, \quad a:=\frac1x-b. \tag{4} $$
Verify that $$ a+b = a\,b = \frac1x, \quad x\,b^2 = b-1. \tag{5} $$
Note that $$ a-b = \frac{\sqrt{1-4x}}x. \tag{6} $$
Equation $(5)$ implies $$ x\,b^{n+1} = b^n-b^{n-1}. \tag{7} $$
Define $$ G_n(x) := \frac{b^n}{x(a-b)}. \tag{8} $$
Equation $(7)$ implies $$ x\,G_{n+1}(x) = G_n(x)-G_{n-1}(x). \tag{9} $$
Verify that the coefficients of the power series $\,G_n(x)\,$
satisfy the same recurrence as equation $(3)$.
Also verify that $$ G_{-1}(x) = F_{-1}(x),\quad G_0(x) = F_0(x). \tag{10} $$
Thus, $\,F_n(x) = G_n(x)\,$ for all integer $\,n\,$ using forward
and backward recursion.
A: You can also prove this by showing that both sides are different expressions for the generating function of the same sequence.
Fix a positive integer $n$ from now on. For a nonnegative integer $m$, let $Q_m$ be the number of lattice paths, that touch the main diagonal (starting from the left bottom corner) exactly $n$ times before it goes above it for the first time in an $m\times m + 1$ grid ($m$ horizontal, $m+1$ vertical). Let us call these paths admissible paths. All paths considered here are only allowed to go right or up.
If such an admissible path exists for some $m$ then $m\ge n$ since for every time you touch the diagonal, from the bottom corner up to the last time you touch the diagonal but failed to go up (i.e. n times) you need an horizontal segment that keeps you below it. So, horizontally you need at least $n$ segments, hence $m\ge n$.
The generating function looks then like this: $\displaystyle\sum_{m\ge n} Q_mx^m$.
Define $k = m - n$. We have:
Claim: There is a bijection between the admissible paths and the paths of an $k\times (n + k)$ grid ($k$ horizontal, $n + k$ vertical segments.)
Proof:
Given an admissible path, we remove the following segments from it: the $n$ horizontal segments that follow a failure point and the one vertical segment that follows the first time we cross (i.e the very first segment that is above the diagonal). We concatenate the resulting pieces by gluing their endpoints one to the next. Notice that the first segment we remove always is the first horizontal segment from the left bottom corner.The path that remains has $m - n = k$ horizontal segments and $m + 1 - 1 = m = n + k$ vertical paths. Thus these paths indeed are in the sought grid.
If we have one such path $P$ in order to read the corresponding admissible path we begin by putting an horizontal segment and we follow $P$ until we hit the main diagonal, at which point we put another horizontal segment, and proceed reading $P$. We put horizontal segments until we have touched the diagonal $n$ times (without counting the initial point). At that time we put a vertical segment, and we copy what is left of $P$. Inverting the computations above we see that this is indeed a path in a grid of $m\times m + 1$.
Notice that because our path $P$ goes up $n + k$ times we must always be able to push it horizontally (force it to fail), counting the first segment from the bottom left corner, n times since, in the worst case scenario (k = 0) after pushing the n times we get we have moved $n + k$ in both directions and we still have the extra room to push up once more. This proves that the constructed path out from $P$ is indeed admissible. This concludes proving this correspondence is actually a bijection. $\blacksquare$
Here is a drawing to show this for $n =2, m = 3, k = 1$:

[The yellow edges are those we add to make sure it fails until we want it to succeed]
We have proven then that the generating function is
$$\begin{equation*}
\displaystyle\sum_{m\ge n} Q_mx^m = \displaystyle\sum_{k\ge 0} \binom{n + 2k}{k}x^{n + k}.
\end{equation*}$$
On the other hand, we can forget about the size of the final grid (i.e. about $m$) and construct what happens out of first principles. There are $n + 1$ independent events ocurring: what happens before the first failure, in between the first and second failures, up to what happens in between the $n - 1$ failure and the success moment and then what happens after we crossed the diagonal and went above for the first times.
Each one of the first independent events is some Catalan number $C_{i}$ and contributes $i + 1$ to the horizontal and vertical lengths, since we must not cross the subdiagonal until the right time. Notice this is important, since if we just consider the $i\times i$ square instead we might have intermidiate failures in between endpoints, since catalan paths are allowed to touch the diagonal of the square they live in, and we dont want those extra failures.
Hence the generating function of each of these events is $x\displaystyle\sum_{i = 0}C_ix^i$ (the extra $x$ is the displacement on the contribution to horizontal length!). We have $n$ of these.
Then, after the last Catalan square is done, we have a foced vertical segment and then whatever we want as long as it happens in a $j\times j$ square for some $j$. (This is because at the end, the final grid has to be $m\times m + 1$ and the Catalan part has produced a square grid and the vertical strip takes awaty the $+1$, so we need another square for the dimensions to match. The generating function for this square is
$$\begin{equation*}
 \displaystyle\sum_{j\ge 0} \binom{2j}{j}x^j
\end{equation*}$$
We have thus proved the equality
$$\begin{equation*}
 \left(x\displaystyle\sum_{i = 0}C_ix^i\right)^n\displaystyle\sum_{j\ge 0} \binom{2j}{j}x^j = \displaystyle\sum_{k\ge 0} \binom{n + 2k}{k}x^{n + k}
\end{equation*}$$
Using that we know
$$\displaystyle\sum_{i = 0}C_ix^i = \dfrac{1 - \sqrt{1 - 4x}}{2x}$$
and, from Newton's Binomial theorem, that
$$
\displaystyle\sum_{j\ge 0} \binom{2j}{j}x^j = \dfrac{1}{\sqrt{1 - 4x}}
$$
we conclude
$$
\begin{equation*}
 x^n\left(\dfrac{1 - \sqrt{1 - 4x}}{2x}\right)^n\dfrac{1}{\sqrt{1 - 4x}} = \displaystyle\sum_{k\ge 0} \binom{n + 2k}{k}x^{n + k},
\end{equation*}
$$
and cancelling the factor $x^n$ on both sides we get the desired equality.
A: Here is an approach based upon the Lagrange inversion theorem. We follow the paper Lagrange Inversion: when and how by R. Sprugnoli etal.
We consider the generating function
\begin{align*}
F(x)=\sum_{k=0}^{\infty}a_kx^k=\sum_{k=0}^\infty\binom{n+2k}{k}x^k
\end{align*}
and apply formula (G6) from the paper. The formula (G6) says that if there are functions $A(u)$ and $\phi(u)$, so that the coefficient $a_k$ admits a representation
\begin{align*}
a_k=[u^k]A(u)\phi(u)^k
\end{align*}
then the following is valid:
\begin{align*}
F(x)&=\sum_{k=0}^{\infty}[u^k]A(u)\phi(u)^kx^k\\
&=\left.\frac{A(u)}{1-x\phi^{\prime}(u)}\right|_{u=x\phi(u)}\tag{1}
\end{align*}

We obtain
\begin{align*}
\color{blue}{F(x)}&\color{blue}{=\sum_{k=0}^\infty\binom{n+2k}{k}x^k}\\
&=\sum_{k=0}^\infty[u^k](1+u)^{n+2k}x^k\tag{2}\\
&=\left.\frac{(1+u)^n}{1-x\,\frac{d}{du}(1+u)^2}\right|_{u=x(1+u)^2}\tag{3}\\
&=\frac{(1+u)^n}{1-\frac{u}{(1+u)^2}\cdot 2(1+u)}\tag{4}\\
&=\frac{(1+u)^{n+1}}{1-u}\tag{5}\\
&=\frac{\left(\frac{1}{2x}\left(1-\sqrt{1-4x}\right)\right)^{n+1}}{2-\frac{1}{2x}\left(1-\sqrt{1-4x}\right)}\tag{6}\\
&\,\,\color{blue}{=\frac{1}{\sqrt{1-4x}}\left(\frac{1-\sqrt{1-4x}}{2x}\right)^n}\tag{7}
\end{align*}
and the claim follows.

Comment:

*

*In (2) we use the coefficient of operator $[x^k]$ to denote the coefficient of a series. We observe we can apply the Lagrange Inversion theorem with $A(u)=(1+u)^n$ and $\phi(u)=(1+u)^2$.


*In (3) we use formula (1) with $A$ and $\phi$ as stated in the comment above.


*In (4) we substitute $x=\frac{u}{1+u}$ and do the derivation.


*In (5) we simplify the expression.


*In (6) we recall $u=x(1+u)^2$ which is a quadratic equation in $u=u(x)$. We calculate
\begin{align*}
u(x)&=\frac{1}{2x}\left(1-2x\pm\sqrt{1-4x}\right)\\
&=\frac{1}{2x}\left(1\pm\sqrt{1-4x}\right)-1
\end{align*}
and take the solution with the minus sign, since this one can be expanded as generating function.


*In (7) we make again some simplifications to obtain the wanted form.
