<s>[INST] How to find the sum $\sum_{k=1}^{\lfloor n/2\rfloor}\frac{2^{n-2k}\binom{n-2}{2k-2}\binom{2k-2}{k-1}}{k}$ Let $n$ be positive integer, find the value
$$f(n)=\sum_{k=1}^{\lfloor n/2 \rfloor}\dfrac{2^{n-2k}\binom{n-2}{2k-2}\binom{2k-2}{k-1}}{k}. $$
I have found
$$ f(2)=1, \quad f(3)=2, \quad f(4)=5, \quad f(5)=14, \quad f(6)=42, \quad f(7)=132. $$
It seem OEIS (A000108):
$$ f(n)=\dfrac{1}{n}\binom{2n-2}{n-1},$$
but how to prove it?
 [/INST] In seeking to evaluate where the sum is zero when $n\lt 2$
$$\sum_{k=1}^{\lfloor n/2\rfloor}
2^{n-2k} {n-2\choose n-2k} \frac{1}{k} {2k-2\choose k-1}$$
we recognize the Catalan number and obtain
$$\sum_{k=1}^{\lfloor n/2\rfloor}
2^{n-2k} {n-2\choose n-2k}
[z^{k}] \frac{1-\sqrt{1-4z}}{2}
\\ = [w^n] (1+w)^{n-2}
\sum_{k=1}^{\lfloor n/2\rfloor}
2^{n-2k} w^{2k}
[z^{k}] \frac{1-\sqrt{1-4z}}{2}.$$
We get a zero contribution when $k=0$ from the coefficient extractor in
$z$ as well as when $2k\gt n$ from the coefficient extractor in $w$ so we
may extend the sum to
$$2^n [w^n] (1+w)^{n-2}
\sum_{k\ge 0}
2^{-2k} w^{2k}
[z^{k}] \frac{1-\sqrt{1-4z}}{2}
\\ = 2^n [w^n] (1+w)^{n-2}
\frac{1-\sqrt{1-w^2}}{2}.$$
This is
$$2^n \;\underset{w}{\mathrm{res}}\;
\frac{1}{w^{n+1}} (1+w)^{n-2}
\frac{1-\sqrt{1-w^2}}{2}.$$
Now we put $w/(1+w) = v$ so that $w=v/(1-v)$ and $dw = 1/(1-v)^2 \; dv$
to get
$$2^n \;\underset{v}{\mathrm{res}}\;
\frac{1}{v^{n+1}} (1-v)^3
\frac{1-\sqrt{1-v^2/(1-v)^2}}{2}
\frac{1}{(1-v)^2}
\\ = 2^n [v^n] \frac{1-v-\sqrt{1-2v}}{2}
= [v^n] \frac{1-2v-\sqrt{1-4v}}{2}
\\ = [v^{n-1}] \frac{1-2v-\sqrt{1-4v}}{2v}
= [v^{n-1}] (-1+\frac{1-\sqrt{1-4v}}{2v}).$$
This is the Catalan number $C_{n-1}$ when $n\ge 2$ and when $n=1$
we get $-1+C_0 = 0.$
</s>