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?

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}. $$

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.$

This is just a supplement to @MarkoRiedel's answer which provides some interesting and powerful techniques. We will heavily use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ of a series. This way we can write for instance \begin{align*} \binom{n}{k}=[z^k](1+z)^n\qquad \qquad [z^k]A(z)=[z^k]\sum_{n=0}^\infty a_nz^n=a_k \end{align*}

We show the following is valid \begin{align*} \color{blue}{f(n)=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}2^{n-2k}\binom{n-2}{2k-2}\frac{1}{k}\binom{2k-2}{k-1} =\frac{1}{n}\binom{2n-2}{n-1}\qquad\qquad n\geq 2}\tag{1} \end{align*}

We observe the left-hand side in (1) contains $C_{k-1}:=\frac{1}{k}\binom{2k-2}{k-1}$ the ubiquituous Catalan numbers which have generating function $c(z)$ with \begin{align*} c(z)=\sum_{k=0}^\infty C_kz^k&=\sum_{k=0}^\infty \frac{1}{k+1}\binom{2k}{k}z^k\\ &=\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\tag{2} \end{align*}

Preparation: We start with a small rearrangement and consider $f(n+2)$ instead of $f(n)$ which has a slightly more convenient representation. We obtain for $n\geq 0$: \begin{align*} f(n+2)&=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor+1}2^{n+2-2k}\binom{n}{2k-2}\frac{1}{k}\binom{2k-2}{k-1}\\ &=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}2^{n-2k}\binom{n}{2k}\color{blue}{\frac{1}{k+1}\binom{2k}{k}}\tag{3}\\ \end{align*} In (3) we shift the index to start with $k=0$ and observe the blue marked term is the $k$-th Catalan number $C_k$.

In the following we want to do the calculations with the help of generating functions. In order to do so we use two key ingredients. One of them is the substitution rule.

Substitution rule: We start with the right-hand side of (3) and obtain \begin{align*} \color{blue}{f(n+2)}&\color{blue}{=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}2^{n-2k}\binom{n}{2k}\frac{1}{k+1}\binom{2k}{k}}\\ &=\sum_{k=0}^\infty2^{n-2k}\binom{n}{n-2k}[z^k]\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\tag{4.1}\\ &=\sum_{k=0}^{\infty}2^{n-2k}[w^{n-2k}](1+w)^n[z^k]\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\tag{4.2}\\ &=[w^n](1+w)^n\sum_{k=0}^{\infty}2^{n-2k}w^{2k}[z^k]\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\tag{4.3}\\ &=2^n[w^n](1+w)^n\sum_{k=0}^{\infty}\left(\frac{w^2}{4}\right)^{k}[z^k]\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\tag{4.4}\\ &=2^n[w^n](1+w)^n\frac{1}{2\left(\frac{w^2}{4}\right)}\left(1-\sqrt{1-4\left(\frac{w^2}{4}\right)}\right)\tag{4.5}\\ &\,\,\color{blue}{=2^n[w^n](1+w)^n\frac{2}{w^2}\left(1-\sqrt{1-w^2}\right)}\tag{4.6}\\ \end{align*}

Comment:

• In (4.1) we write $C_k$ using the generating function as in (1) and (2). We also use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$. This enables us to set the upper limit of the sum to infinity since $\binom{n}{n-2k}=0$ if $k>\left\lfloor\frac{n}{2}\right\rfloor$.

• In (4.2) we use the coefficient of operator again as indicated in (1).

• In (4.3) we use the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$ and factor out terms independent of the index variable $k$.

• In (4.4) and (4.5) we apply the substitution rule \begin{align*} A(w)=\sum_{k=0}^\infty a_k w^k=\sum_{k=0}^\infty \left([z^k]A(z)\right)w^k=\sum_{k=0}^\infty w^k\left([z^k]A(z)\right) \end{align*}

• In (4.6) we do some simplifications.

Intermezzo: Change of variables under the res sign

When looking at (4.6) we can say we have made some simplifications of the generating functions but we still cannot derive a simple expression when calculating the coefficient of $w^n$ due to the term $\color{blue}{(1+w)^n}$ which gives a sum when doing the expansion. This is the situation where the second key ingredient comes into play. We use a technique called change of variables under the res sign which automagically removes this obstacle. This technique uses behind the curtain (formal) residues. Here we hide residues by using the coefficient of operator and state the rule as follows:

\begin{align*} &[w^{n}]\left(A(w)f^{n}(w)\right)=[u^{n}] \left(\left.\left[A(w)\left(f(w)\left(\frac{w}{f(w)}\right)^{\prime}\right)^{-1}\right] \right|_{w=g(u)}\right)\tag{5.1} \end{align*} where we use the substitution: \begin{align*} \color{blue}{u=u(w)=\frac{w}{f(w)}}\tag{5.2} \end{align*}

In (5.1) we have a generating function $A(w)$, a generating function $f(w)$ with constant term $\ne 0$ and $w=g(u)$ is the (unique) solution of (5.2).

In the current situation (4.6) we have \begin{align*} A(w)=\frac{2}{w^2}\left(1-\sqrt{1-w^2}\right)\qquad f(w)=1+w \end{align*} and use according to (5.2) the substitution \begin{align*} u(w)=\frac{w}{1+w}\qquad \to\qquad \color{blue}{w=\frac{u}{1-u}}\tag{6.1} \end{align*}

Calculation of the derivative gives \begin{align*} w^{\prime}(u)=\left(\frac{u}{1-u}\right)^{\prime}=\frac{1}{(1-u)^2}\tag{6.2} \end{align*}

Second part:

We can now continue with the expression (4.6). We apply the substitution rule (5.1) by using the substitution (6.1) and (6.2) and we obtain for $n\geq 0$:

\begin{align*} &\color{blue}{f(n+2)}\\ &\quad\color{blue}{=2^n[u^n]\left.\left(\frac{2}{w^2}\left(1-\sqrt{1-w^2}\right)\frac{1}{(1-u)^2}\,\frac{1}{1+w}\right)\right|_{w=\frac{u}{1-u}}}\\ &\quad=2^n[u^n]\left(\frac{2(1-u)^2}{u^2}\left(1-\sqrt{1-\frac{u^2}{(1-u)^2}}\right)\frac{1}{(1-u)^2}\,\frac{1}{1+\frac{u}{1-u}}\right)\\ &\quad=2^n[u^n]\left(\frac{2(1-u)^2}{u^2}\left(1-\frac{\sqrt{1-2u}}{1-u}\right)\frac{1}{(1-u)^2}\,(1-u)\right)\\ &\quad=2^{n+1}[u^{n+2}]\left(1-u-\sqrt{1-2u}\right)\tag{7.1}\\ &\quad=2^{n+1}[u^{n+1}]\frac{1-u-\sqrt{1-2u}}{u}\\ &\quad=[u^{n+1}]\frac{1-2u-\sqrt{1-4u}}{2u}\tag{7.2}\\ &\quad=[u^{n+1}]\left(\frac{1-\sqrt{1-4u}}{2u}-1\right)\tag{7.3}\\ &\quad=[u^{n+1}]\frac{1-\sqrt{1-4u}}{2u}\tag{7.4}\\ &\quad\,\,\color{blue}{=C_{n+1}} \end{align*} and the claim (1) follows.

Comment:

• In (7.1) and the steps before we did some simplifications. We finally want to include the factor $2^{n+1}$ into the generating function. We do this by synchronising the exponent of $u$ in the next line once more by applying the rule as in (4.3).

• In (7.2) we incorporate the factor $2^{n+1}$ by substituting $u\to 2u$.

• In (7.3) we can skip the constant term $-1$ since $n\geq 0$.

• In (7.4) we finally get the generating function $c(u)$ of the Catalan numbers.

Note: The techniques presented here can be found in the classic Integral Representation and the Computation of Combinatorial Sums by G. P. Egorychev. A two-dimensional application of the change of variables under the res sign is given in this MSE-post.

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 ^_^

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.