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?
 A: Shifting the summation index by $1$, let us rewrite $f(n)$ by
$$ f(n) = \sum_{k \geq 0} \binom{n-2}{2k} \cdot 2^{n-2-2k} \cdot \frac{1}{k+1}\binom{2k}{k}. $$
We seek for a combinatorial interpretation of this sum.
1. (A brief review on Dyck words) A Dyck word of length $2n$ is a string consisting of $n$ $\mathtt{u}$'s and $n$ $\mathtt{d}$'s such that no initial segment of the string has more $\mathtt{d}$'s than $\mathtt{u}$'s.
Then it is well-known that the Catalan number,
$$C_n = \frac{1}{n+1}\binom{2n}{n}, $$
counts the number of all Dyck words of length $2n$.

Example. There are five Dyck words of length $6$:
$$ \mathtt{uuuddd}, \qquad \mathtt{uduudd}, \qquad \mathtt{ududud}, \qquad \mathtt{uuddud}, \qquad \mathtt{uududd}. $$
So $C_3 = 5$.

2. (Modified Dyck words) Now we introduce a generalization of Dyck word. A string $w$ in alphabet $\{\mathtt{X}, \mathtt{Y}, \mathtt{U}, \mathtt{D}\}$ is called a modified Dyck word if

*

*$w$ contains equal number of $\mathtt{U}$'s and $\mathtt{D}$'s, and

*No initial segment of $w$ has more $\mathtt{D}$'s than $\mathtt{U}$'s.

In other words, the string obtained by removing $\mathtt{X}$'s and $\mathtt{Y}$'s in $w$ is a Dyck word. Equivalently, a modified Dyck word is any string obtained from a Dyck word in alphabet $\{\mathtt{U}, \mathtt{D}\}$ by splicing arbitrary number of $\mathtt{X}$'s and $\mathtt{Y}$'s.
Now the importance of the modified Dyck words comes from the following lemma:

Lemma. For each $n \geq 1$, there is a bijection
$$
\left\{ \begin{gathered}
\text{modified Dyck words of length $n-1$} \\
\text{in alphabet $\{\mathtt{X}, \mathtt{Y}, \mathtt{U}, \mathtt{D}\}$}
\end{gathered} \right\}
\quad\longleftrightarrow\quad
\left\{ \begin{gathered}
\text{Dyck words of length $2n$} \\
\text{in alphabet $\{\mathtt{u}, \mathtt{d}\}$}
\end{gathered} \right\}
$$
that maps each modified Dyck word $w$ to the word $\mathtt{u}w\mathtt{d}$ via the correspondence
$$ \mathtt{X} \to \mathtt{ud}, \qquad \mathtt{Y} \to \mathtt{du}, \qquad \mathtt{U} \to \mathtt{uu}, \qquad \mathtt{D} \to \mathtt{dd}. \tag{*}$$

The intuition behind this bijection is as follows: We identify each Dyck word of length $2n$ with the lattice path from $(0, 0)$ to $(2n, 0)$ by identifying $\mathtt{u} = \nearrow$ and $\mathtt{d} = \searrow$. For example,

From the definition, a string in alphabet $\{\mathtt{u}, \mathtt{d}\}$ is a Dyck word if and only if the corresponding lattice path is a Dyck path (a path that lies on and above the horizontal axis).
Now, by dropping the first and last moves from a Dyck path joining $(0, 0)$ to $(2n, 0)$, grouping the rest into pairs of adjacent moves, we see that the truncated path becomes a modified Dyck path:

Conversely, starting from any modified Dyck paths (using four types of moves in $\text{(*)}$) we can recover the Dyck path by reversing the above construction. This is why we expect the lemma to hold.
3. (Solution) Now we are ready to investigate $f(n)$.
\begin{align*}
C_n
&= [\text{# of Dyck words of length $2n$}] \\
&= \sum_{k\geq 0} [\text{# of modified Dyck words of length $n-1$ containing $k$ $\mathtt{U}$'s}] \\
&= \sum_{k\geq 0} C_k \cdot [\text{# of ways of splicing $\mathtt{X}$ and $\mathtt{Y}$'s to obtain a string of length $n-1$}] \\
&= \sum_{k\geq 0} C_k \cdot \binom{n-1}{2k} 2^{n-1-2k} \\
&= f(n+1).
\end{align*}
Therefore
$$ f(n) = C_{n-1} = \frac{1}{n} \binom{2n-2}{n-1}. $$
A: This sum is hypergeometric, and so there is an algorithm which will evaluate it to a closed form when possible. See Knuth, Graham, and Patashnik's Concrete Mathematics or Petkovsek, Wilf, and Zeilberger's A=B for more information.
With this in mind, we can ask wolframalpha to solve this sum, and it tells us the answer is
$$
\frac{4^{n-1} \left ( n - \frac{3}{2} \right )!}{\sqrt{\pi} n!}
$$
But, we know that
$$
\left ( n - \frac{3}{2} \right )! = 
\left ( - \frac{1}{2} + n-1 \right )! = 
\frac{\sqrt{\pi} \left ( 2 (n-1) \right )!}{4^{n-1} (n-1)!}
$$
and plugging this into the above expression tells us that this sum is equal to
$$
\frac{(2 (n-1))!}{n! (n-1)!}
$$
If we reindiex $m = n-1$, this becomes
$$
\frac{(2m)!}{(m+1)! m!}
$$
which we recognize as the $m$th Catalan Number, agreeing with your OEIS entry.

If you don't like using computer algebra systems, then you could always run the hypergeometric sum algorithm by hand to get the same answer (albeit with substantially more tedium). The Catalan Numbers are ubiquitous in combinatorics, and so there may be a more satisfying bijective proof of your sum. But without knowing where your sum came from, it's hard to guess what that might be. At the very least, this provides a proof that the conjectured identity is correct.

I hope this helps ^_^
A: 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.$
A: Given the sequence function definition
$$ f(n) :=\sum_{k=1}^{\lfloor n/2\rfloor}F_{n,k}\tag{1} $$
where
$$ F_{n,k} := \dfrac{2^{n-2k}\binom{n-2}{2k-2}
  \binom{2k-2}{k-1}}{k}, \tag{2} $$
note that $\,F_{n,k} = T(n\!-\!1,k\!-\!1)\,$ for $\,n\!>\!1\,$ where $\,T\,$ is given in the
OEIS sequence
A091894
whose sequence NAME is

Triangle read by rows: $T(n,k)$ is the number of Dyck paths of semilength $n$, having $k$ ddu's [here $u$ = (1,1) and $d$ = (1,-1)].

and whose first FORMULA entry is

$$ T(n,k) = 2\text{^}(n\!-\!2\!*\!k\!-\!1)\!*\!\text{binomial} (n\!-\!1,2\!*\!k)\!*\!\text{binomial}(2\!*\!k,k)/(k\!+\!1),
\;T(0,0) = 1, \text{ for } 0 <= k <=
 \text{floor}((n\!-\!1)/2).$$

The first COMMENT entry includes this:

Row sums are the Catalan numbers (A000108).

More precisely, $\,f(n) = C_{n-1} = \binom{2n-2}{n-1}/n\,$ but how to prove it?
One method uses generating function power series and the
Umbral calculus.
Define the Catalan number generating function
$$ C(x) := \sum_{n=0}^\infty C_n x^n = 
\frac{1-\sqrt{1-4x}}{2x}. \tag{3} $$
Define the triangular sequence
$$ U_{n,k} := 2^{n-2k}\binom{n-2}{2k-2}. \tag{4} $$
Note that equations $(1)$, $(2)$ and $(4)$ combine to get
$$ f(n) = \sum_{k=1}^{\lfloor n/2 \rfloor} U_{n,k}\,C_{k-1} \tag{5} $$
and if the recursion equation
(where $n>1$ and with $C_0=1$)
$$ C_{n-1}=\sum_{k=1}^{\lfloor n/2 \rfloor} U_{n,k}\,C_{k-1} \tag{6}$$
is proved then we are done.
The following proof uses Umbral calculus.
Given the formal variable $\,c,\,$ define the formal
power series linear operator
$$ L\!\!\left[\sum_{n=0}^\infty a_nc^n\right] :=
  \sum_{n=0}^\infty a_nC_{n-1}. \tag{7} $$
Note that this yields
$$ L\!\!\left[\frac{cx}{1-cx}\right] = 
  L\!\!\left[\sum_{n=1}^\infty c^nx^n\right] =
 \sum_{n=1}^\infty C_{n-1}x^n = x\,C(x). \tag{8} $$
Define the rational expressions
$$ U := (1-2x)\frac{c\,t}{1-c\,t},\quad \text{ where }\quad t:=\frac{x^2}{(1-2x)^2}. \tag{9} $$
The expansion of $\,U\,$ as a power series in $\,x\,$ is
$$ U = (c)x^2 + (2c)x^3 + (4c+c^2)x^4 + (8c+6c^2)x^5 + \dots. \tag{10} $$
Note that this is expressed as the summation
$$ U = \sum_{n=2}^\infty \left(\sum_{k=1}^\infty 
U_{n,k}\,c^k\right) x^n \tag{11}$$
which comes from expanding the binomial series
$$ (1\!-\!2x)(c\,t)^{2k} \!=\!
  \frac{c^k x^{2k}}{(1\!-\!2x)^{2k-1}}
 \!=\! \sum_{n=2k}^\infty c^k 2^{n-2k} 
 \binom{n-2}{2k-2}x^n. \tag{12}$$
Combine equations $(7)$ and $(11)$ to get
$$ L[U] = \sum_{n=2}^\infty \left(\sum_{k=1}^\infty 
 U_{n,k}\,C_{k-1}\right)\! x^n. \tag{13} $$
Combine equations $(8)$ and $(9)$ to get
$$ L[U] = (1-2x)\,L\!\!\left[\frac{c\,t}{1-c\,t}\right]
= (1-2x)\,t\,C(t) \tag{14} $$
and with some simple algebra to get
$$ L[U] = \frac{(1-2x)-\sqrt{1-4x}}2 =
  x\,C(x)-x. \tag{15} $$
This, combined with equations $(8)$ and $(13)$, proves
equation $(6)$ Q.E.D.
A: We have the integral formula  for the Catalan numbers $C_k = \frac{\binom{2k}{k}}{k+1}$ :
$$\ \ \frac{C_k}{2^{2k+1}}=\frac{1}{\pi}\int_{-1}^1 t^{2k}\sqrt{1-t^2} dt \ \ (*)$$
Note also that
$0 = \frac{1}{\pi} \int_{-1}^{1} x^{2k+1} \sqrt{1-x^2} dx$.  Therefore we get
$$(**) \ \ \sum_{k} \binom{n}{2k} \frac{C_{k}}{2^{2k+1}} = \frac{1}{\pi} \int_{-1}^1 (\sum_{k=0}^n \binom{n}{k} x^k) \sqrt{1-x^2} dx =\\ =\frac{1}{\pi} \int_{-1}^1 (1+x)^n \sqrt{1-x^2} dx$$
Now use another formula for the Catalan numbers
$$ C_n = \frac{2^n}{\pi} \int_{-1}^1 (1+x)^{n-1} \sqrt{1-x^2} d x\ \ (***)$$
We are done.
Another possible approach: use the binomial transform for the sequence $\frac{C_{k}}{2^{2k+1}}$ at even index $2k$ and $0$ otherwise. We have the generating function
$$f(x)= \sum_{k\ge 0} \frac{C_{k}}{2^{2k+1}} x^{2k} = \frac{1-\sqrt{1-x^2}}{x^2}$$
Now use that the generating function for the transformed sequence equals $g(x) = \frac{1}{1-x} \cdot f(\pm \frac{x}{1-x})$ ($f$ even so both $\pm$ are OK).  We get
$$g(x) = \frac{1- \sqrt{1- 2 x} - x}{x^2}= \sum_{n\ge 0}\frac {C_{n+1}}{2^{n+1}} x^n$$
Conclusion
$$(**) = \frac{C_{n+1}}{2^{n+1}}$$
$\bf{Added:}$
The formulas $(*),(***)$ are equivalent to the representation of Catalan number as moments of a distribution on $[0,4]$.
$$C_n = \frac{1}{2\pi} \int_{0}^4 t^n  \sqrt{\frac{4-t}{t}} \, dt$$
