I want to show that the determinant of the matrix $A$ of order $n\times n$ with entries $a_{ij}=C_{i+j-2}$ is $1$, where $C_m$ is the $m$th term of the Catalan sequence. To solve this problem, the hint is defining a decomposition $LU$ of $A$.
Set $\,u_{ij}\,$ to be $$ u_{ij} = \frac{2i+1}{i+j+1}{2j \choose j-i}, $$ and let $\,U_n = (u_{ij})_{0\le i,j\le n-1},\,$ which is an $\,n\times n\,$ upper triangle matrix whose diagonal entries are $\,1.\,$ Put $\,L_n = \,^{t}U_{n}.\,$ Then we can show that $\,C_n^0 = L_nU_n,\,$ which immediately implies that $\,\det C_n^0 = 1.\,$ We omit the detail but one can easily prove that these $\,LU$-decompositions reduce to the following identity: $$ \sum_{k\ge 0} \frac{(2k+1)^2}{(i+k+1)(j+k+1)} {2i \choose i-k}{2j \choose j-k} = \frac1{i+j+1} {2i+2j \choose i+j}. $$
My question is regarding the U matrix, I don't know why it is triangular, but in case such how can I prove the mentioned identity?
Original image: https://i.stack.imgur.com/xcDM3.png
Introduction
The identity
$$\sum_{k\ge 0} \frac{(2k+1)^2}{(p+k+1)(q+k+1)} {2p\choose p-k} {2q\choose q-k} = \frac{1}{p+q+1} {2p+2q\choose p+q}$$
is identical to
$$\sum_{k=0}^{\min(p,q)} (2k+1)^2 {2p+1\choose p+k+1} {2q+1\choose q+k+1} = \frac{(2p+1)(2q+1)}{p+q+1} {2p+2q\choose p+q}$$
or
$$\sum_{k=0}^{\min(p,q)} (2k+1)^2 {2p+1\choose p-k} {2q+1\choose q-k} = \frac{(2p+1)(2q+1)}{p+q+1} {2p+2q\choose p+q}.$$
The LHS is
$$S= [z^p] (1+z)^{2p+1} [w^q] (1+w)^{2q+1} \sum_{k=0}^{\min(p,q)} (2k+1)^2 z^k w^k.$$
The two coefficient extractors enforce the upper limit of the sum:
$$[z^p] (1+z)^{2p+1} [w^q] (1+w)^{2q+1} \sum_{k\ge 0} (2k+1)^2 z^k w^k \\ = [z^p] (1+z)^{2p+1} [w^q] (1+w)^{2q+1} \frac{z^2 w^2 + 6 z w + 1}{(1-zw)^3} \\ = - [z^p] \frac{1}{z^3} (1+z)^{2p+1} [w^q] (1+w)^{2q+1} \frac{z^2 w^2 + 6 z w + 1}{(w-1/z)^3} \\ = - [z^{p+3}] (1+z)^{2p+1} [w^q] (1+w)^{2q+1} \frac{z^2 w^2 + 6 z w + 1}{(w-1/z)^3}.$$
The coefficient extractor in $w$ is
$$\mathrm{Res}_{w=0} \frac{1}{w^{q+1}} (1+w)^{2q+1} \frac{z^2 w^2 + 6 z w + 1}{(w-1/z)^3}.$$
Residue at infinity
Now residues sum to zero and the residue at infinity is given by
$$-\mathrm{Res}_{w=0} \frac{1}{w^2} w^{q+1} \frac{(1+w)^{2q+1}}{w^{2q+1}} \frac{z^2/w^2 + 6 z/w + 1}{(1/w-1/z)^3} \\ = -\mathrm{Res}_{w=0} \frac{(1+w)^{2q+1}}{w^{q+2}} \frac{z^2 w + 6 z w^2 + w^3}{(1-w/z)^3} \\ = -\mathrm{Res}_{w=0} \frac{(1+w)^{2q+1}}{w^{q+1}} \frac{z^2 + 6 z w + w^2}{(1-w/z)^3}.$$
Next applying the coefficient extractor in $z$ we find
$$\mathrm{Res}_{z=0} \frac{(1+z)^{2p+1}}{z^{p+4}} \mathrm{Res}_{w=0} \frac{(1+w)^{2q+1}}{w^{q+1}} \frac{z^2 + 6 z w + w^2}{(1-w/z)^3} \\ = \mathrm{Res}_{z=0} \frac{(1+z)^{2p+1}}{z^{p+2}} \mathrm{Res}_{w=0} \frac{(1+w)^{2q+1}}{w^{q+1}} \frac{1 + 6 w/z + w^2/z^2}{(1-w/z)^3} \\ = \mathrm{Res}_{z=0} \frac{(1+z)^{2p+1}}{z^{p+2}} \mathrm{Res}_{w=0} \frac{(1+w)^{2q+1}}{w^{q+1}} \sum_{k\ge 0} (2k+1)^2 \frac{w^k}{z^k} \\ = \sum_{k\ge 0} (2k+1)^2 {2p+1\choose p+k+1} {2q+1\choose q-k} = S.$$
This means that $S$ is minus half the residue at $w=1/z$, substituted into the coefficient extractor in $z.$
Residue at $w=1/z$
The residue at $w=1/z$ is
$$\mathrm{Res}_{w=1/z} \frac{1}{w^{q+1}} (1+w)^{2q+1} \frac{z^2 w^2 + 6 z w + 1}{(w-1/z)^3} \\ = \mathrm{Res}_{w=1/z} \frac{1}{w^{q+1}} (1+w)^{2q+1} \left(\frac{8}{(w-1/z)^3} + \frac{8z}{(w-1/z)^2} + \frac{z^2}{w-1/z}\right).$$
Evaluating the three pieces in turn we start with
$$8\frac{1}{2}\left(\frac{ (1+w)^{2q+1}}{w^{q+1}}\right)'' = 4 (q+1)(q+2)\frac{(1+w)^{2q+1}}{w^{q+3}} \\ - 8(q+1)(2q+1)\frac{(1+w)^{2q}}{w^{q+2}} + 4 (2q+1)(2q)\frac{(1+w)^{2q-1}}{w^{q+1}}.$$
Evaluate at $w=1/z$ to get
$$4(q+1)(q+2) \frac{(1+z)^{2q+1}}{z^{q-2}} \\ - 8 (q+1)(2q+1) \frac{(1+z)^{2q}}{z^{q-2}} + 4 (2q+1)(2q) \frac{(1+z)^{2q-1}}{z^{q-2}}.$$
Substituting into the coefficient extractor in $z$ we find
$$- 4(q+1)(q+2) {2p+2q+2\choose p+q+1} \\ + 8 (q+1)(2q+1) {2p+2q+1\choose p+q+1} - 4 (2q+1)(2q) {2p+2q\choose p+q+1}.$$
Continuing with the middle piece we have
$$8z\left(\frac{ (1+w)^{2q+1}}{w^{q+1}}\right)' = -8z (q+1) \frac{(1+w)^{2q+1}}{w^{q+2}} +8z (2q+1) \frac{(1+w)^{2q}}{w^{q+1}}.$$
Evaluate at $w=1/z$ to get
$$-8(q+1) \frac{(1+z)^{2q+1}}{z^{q-2}} + 8(2q+1) \frac{(1+z)^{2q}}{z^{q-2}}.$$
The coefficient extractor now yields
$$8(q+1) {2p+2q+2\choose p+q+1} - 8(2q+1) {2p+2q+1\choose p+q+1}.$$
The third and last piece produces
$$\frac{(1+z)^{2q+1}}{z^{q-2}}$$
which when substituted into the coefficient extractor yields
$$-{2p+2q+2\choose p+q+1}.$$
Collecting the three pieces
We get
$$-(2q+1)^2 {2p+2q+2\choose p+q+1} + 8q (2q+1) {2p+2q+1\choose p+q+1} - 8q (2q+1) {2p+2q\choose p+q+1} \\ = -(2q+1)^2 {2p+2q+2\choose p+q+1} + 8q (2q+1) {2p+2q\choose p+q} \\ = - 2 (2q+1)^2 {2p+2q+1\choose p+q} + 8q (2q+1) {2p+2q\choose p+q} \\ = - 2 (2q+1)^2 \frac{2p+2q+1}{p+q+1} {2p+2q\choose p+q} + 8q (2q+1) {2p+2q\choose p+q} \\ = -2 \frac{(2p+1)(2q+1)}{p+q+1} {2p+2q\choose p+q}.$$
Halve this value and flip the sign to obtain the coveted
$$\bbox[5px,border:2px solid #00A000]{ \frac{(2p+1)(2q+1)}{p+q+1} {2p+2q\choose p+q}.}$$