# How can I simplify this combinatorics expression?

I got a expression that is related to the combinatorics, and it looks like this:

$$\sum_{k=1}^n \frac{2^{2k-1}}{k}\binom{2n-2k}{n-k}\cdot \frac{1}{\binom{2n}{n}}$$

it is from a question I've been studying, and with another approach, I got the answer:

$$\sum_{k=1}^n\frac{1}{2k-1}$$

so I think the two should be the same, which means that

$$\sum_{k=1}^n \frac{2^{2k-1}}{k}\binom{2n-2k}{n-k}\cdot \frac{1}{\binom{2n}{n}}=\sum_{k=1}^n\frac{1}{2k-1}$$

and to verify this, I wrote a python program to justify. And the outcome is that the two are very likely to be the same. (I tried when $$n=1$$ to $$n=50$$, and the difference is tiny) So can anyone help me to prove it? I've tried many ways but all failed, I even asked chat-gpt but it didn't help. Thanks a lot if you can think of a way to prove it

• If you got the two expressions from the same conbinatorics problem, then you have proved they are equal. Are you looking for an algebraic proof? Apr 24 at 4:48
• Yes, if there's an algebraic proof, it may be more fascinating because it doesn't care about the background Apr 24 at 4:56

## 3 Answers

(I found the proof, it's shown below, after the Update)

(previous:) I simplified your expression

$$$$\frac{\binom{2n-2k}{n-k}}{\binom{2n}{n}}=\frac{(2n-2k)!(n!)^2}{(2n)!((n-k)!)^2}=\frac{(n\cdot(n-1)\dots(n-k+1))^2}{2n\cdot(2n-1)\dots(2n-2k+2)}\\ =\frac{1}{2^{2k}}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n-2k+2}{2n-2k+1}$$$$ So the equation in question becomes $$\sum_{k=1}^n\frac{1}{2k}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n-2k+2}{2n-2k+1}=\sum_{k=1}^n\frac{1}{2k-1}$$ The first few $$n$$ gives:

$$\frac{1}{2}\frac{2}{1}=1$$ $$\frac{1}{2}\frac{4}{3}+\frac{1}{4}\frac{4}{3}\frac{2}{1}=1+\frac{1}{3}$$ $$\frac{1}{2}\frac{6}{5}+\frac{1}{4}\frac{6}{5}\frac{4}{3}+\frac{1}{6}\frac{6}{5}\frac{4}{3}\frac{2}{1}=1+\frac{1}{3}+\frac{1}{5}$$ $$\frac{1}{2}\frac{8}{7}+\frac{1}{4}\frac{8}{7}\frac{6}{5}+\frac{1}{6}\frac{8}{7}\frac{6}{5}\frac{4}{3}+\frac{1}{8}\frac{8}{7}\frac{6}{5}\frac{4}{3}\frac{2}{1}=1+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}$$ I tried to use induction on it, but didn't get anywhere.

On the other hand, I tried to group the terms on the l.h.s, and I got $$\frac{8}{7}\left(\frac{1}{2}+\frac{6}{5}\left(\frac{1}{4}+\frac{4}{3}\left(\frac{1}{6}+\frac{2}{1}\left(\frac{1}{8}\right)\right)\right)\right)=1+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}$$ An interesting thing that I noticed is, if I replace the numbers $$\frac{1}{2},\frac{1}{4},\frac{1}{6},\frac{1}{8}$$ with ones, it suddenly becomes obvious. We get this identity: $$\frac{8}{7}\left(1+\frac{6}{5}\left(1+\frac{4}{3}\left(1+\frac{2}{1}1\right)\right)\right)=8=2+2+2+2$$ Then I wondered, what if I inverse the order of them? And I found that $$\frac{8}{7}\left(\frac{1}{8}+\frac{6}{5}\left(\frac{1}{6}+\frac{4}{3}\left(\frac{1}{4}+\frac{2}{1}\left(\frac{1}{2}\right)\right)\right)\right)=\left(1+\frac{1}{1}\right)\left(1+\frac{1}{3}\right)\left(1+\frac{1}{5}\right)\left(1+\frac{1}{7}\right)-1$$ Because we start with $$a_1=1$$, then we have $$a_2=\frac{4}{3}(\frac{1}{4}+1)=1+\frac{2}{3}$$, next we have $$\frac{6}{5}(\frac{1}{6}+a_2)=\frac{1}{5}+a_2+\frac{1}{5}a_2=a_2+\frac{1}{5}(1+a_2)=1+\frac{2}{3}+\frac{1}{5}(2+\frac{2}{3})=1+\frac{2}{3}+\frac{2}{5}+\frac{2}{3\cdot 5}$$. It's not as obvious as the previous equation, but still pretty easy to prove.

I don't know if this is in the right direction of proving the equation in question, but it seems that this construction gives some interesting sequences, and I wonder what other sequences can be constructed by different sequences of coefficients.

## Update

I found a proof by induction:

Suppose we already have $$\sum_{k=1}^n\frac{1}{2k}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n-2k+2}{2n-2k+1}=\sum_{k=1}^n\frac{1}{2k-1}\label{eq1}\tag{1}$$ We want to prove that $$\sum_{k=1}^{n+1}\frac{1}{2k}\frac{2n+2}{2n+1}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n+2-2k+2}{2n+2-2k+1}=\sum_{k=1}^{n+1}\frac{1}{2k-1}\label{eq2}\tag{2}$$ Multiply $$Eq.\eqref{eq2}$$ by $$2n+1$$, it becomes $$\frac{2n+2}{2}+\sum_{k=2}^{n+1}\frac{2n+2}{2k}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n+2-2k+2}{2n+2-2k+1}=\sum_{k=1}^{n+1}\frac{2n+1}{2k-1}$$ We can re-number $$k$$ on the l.h.s, $$\frac{2n+2}{2}+\sum_{k=1}^{n}\frac{2n+2}{2k+2}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n+2-2k}{2n+2-2k-1}=\sum_{k=1}^{n+1}\frac{2n+1}{2k-1}\label{eq3}\tag{3}$$ Multiply $$Eq.\eqref{eq1}$$ by $$2n+1$$, then subtract that from $$Eq.\eqref{eq3}$$. On the l.h.s, the terms in the summation match up. On the r.h.s, the first $$n$$ terms are cancelled, only the last term $$\frac{2n+1}{2n+1}$$ remains, which is one. So we want to prove that, $$n+1+\sum_{k=1}^{n}\left(\frac{2n+2}{2k+2}-\frac{2n+1}{2k}\right)\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n-2k+2}{2n-2k+1}=1$$ Or, re-arrange it, $$n=\sum_{k=1}^{n}\left(\frac{2n+1}{2k}-\frac{2n+2}{2k+2}\right)\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n-2k+2}{2n-2k+1}$$ $$2n=\sum_{k=1}^{n}\left(\frac{2n+1}{k}-\frac{2n+2}{k+1}\right)\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n-2k+2}{2n-2k+1}$$ $$2n=\sum_{k=1}^{n}\left(\frac{2n-k+1}{k(k+1)}\right)\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{2n-2k+2}{2n-2k+1}\label{eq4}\tag{4}$$ Now, let's work backwards. Starting from the last term on the r.h.s, where $$k=n$$, which is $$\left(\frac{n+1}{n(n+1)}\right)\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{4}{3}\frac{2}{1}=\frac{1}{n}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{4}{3}\frac{2}{1}$$ To combine this with the previous term, we take $$\frac{2}{1}$$ to the front, and multiply to $$\frac{1}{n}$$. Adding this to the previous term, we get $$\left(\frac{2}{n}+\frac{n+2}{(n-1)n}\right)\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{4}{3}=\frac{3}{n-1}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{4}{3}=\frac{4}{n-1}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{6}{5}$$ Next, combine with the previous term, we get $$\left(\frac{4}{n-1}+\frac{n+3}{(n-2)(n-1)}\right)\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{6}{5}=\frac{5}{n-2}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{6}{5}=\frac{6}{n-2}\frac{2n}{2n-1}\frac{2n-2}{2n-3}\dots\frac{8}{7}$$

I think, at this point, the pattern is pretty obvious. Formally, let's set $$t=n-k+1$$ which is just $$k$$ in reverse order, if the previous term gives a $$\frac{2t+1}{n-t}$$, then we can combine it with the previous term, and the coefficient becomes $$\frac{2t+1}{n-t}\frac{2t+2}{2t+1}+\frac{n+t+2}{(n-t-1)(n-t)}=\frac{2t+3}{n-t-1}$$ Eventually we arrive at the first term: $$\frac{2n-1}{1}\frac{2n}{2n-1}=2n$$ which is the same as the l.h.s of $$Eq.\eqref{eq4}$$. The proof is complete.

It took me the entire night, manipulating the equations of $$n=4$$ and $$n=3$$, trying to see a pattern. Finally, I noticed that after some manipulation similar to the one above, the numbers magically cancelled out! I thought, hey, maybe I'm on the right track! And I tested with arbitrary $$n$$ and it worked! It took some effort but it's totally worth it!

I think this is a really neat result. I wonder if there is a simpler proof.

• The proof is so brilliant and wonderful ! Thanks. Wish you good luck. Apr 25 at 3:55

$$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{{\displaystyle #1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\on}[1]{\operatorname{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\sr}[2]{\,\,\,\stackrel{{#1}}{{#2}}\,\,\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$$ \begin{align} & \color{#44f}{\sum_{k = 1}^{n}{2^{2k - 1} \over k}{2n - 2k \choose n - k}{1 \over {2n \choose n}}} \\[5mm] = & \ {1 \over {\, -1/2\,\, \choose n}\pars{-4}^{n}}\sum_{k = 1}^{n} {2^{2k - 1} \over k}{-1/2 \choose n - k}\pars{-4}^{n - k} \\[5mm] = & \ {1\over 2{\, -1/2\,\, \choose n}}\sum_{k = 1}^{n} {\pars{-1}^{k} \over k}{-1/2 \choose n - k} \\[5mm] = & \ {1\over 2{\, -1/2\,\, \choose n}}\sum_{k = 1}^{n} {\pars{-1}^{k} \over k}\bracks{z^{n - k}} \pars{1 + z}^{-1/2} \\[5mm] = & \ {1\over 2{\, -1/2\,\, \choose n}} \bracks{z^{n}}\pars{1 + z}^{-1/2} \sum_{k = 1}^{\color{red}{\infty}}{\pars{-z}^{k} \over k}\label{1}\tag{1} \\[5mm] = & \ {1\over 2{\, -1/2\,\, \choose n}}\bracks{z^{n}} \pars{1 + z}^{-1/2}\, \braces{-\ln\pars{1 - \bracks{-z}}} \\[5mm] = & \ -\,{1\over 2{\, -1/2\,\, \choose n}} \bracks{z^{n}} \left.\partiald{\pars{1 + z}^{\nu}}{\nu}\right\vert_{\nu\ =\ -1/2} \\[5mm] = & \ -\,{1\over 2{\, -1/2\,\, \choose n}} \left.\partiald{}{\nu}{\nu \choose n} \right\vert_{\nu\ =\ -1/2} \\[5mm] = & \ -\,{1\over 2{\, -1/2\,\, \choose n}} {-1/2 \choose n} \left.\partiald{}{\nu} \ln\pars{\Gamma\pars{\nu + 1} \over \Gamma\pars{\nu - n + 1}} \right\vert_{\nu\ =\ -1/2} \\[5mm] = & \ {1\over 2}\bracks{\Psi\pars{{1 \over 2} - n} - \Psi\pars{1 \over 2}} \\[5mm] \sr{n\ \in\ \mathbb{N}}{=} & \ {1\over 2}\bracks{\Psi\pars{{1 \over 2} + n} - \Psi\pars{1 \over 2}} \\[5mm] = & \ {1\over 2}\sum_{k = 0}^{\infty}\pars{% {1 \over k + 1/2} - {1 \over k + 1/2 + n}} \\[5mm] = & \ {1\over 2}\sum_{k = 0}^{n - 1}{1 \over k + 1/2} = \bbx{\color{#44f}{% \sum_{k = 1}^{n}{1 \over 2k - 1}}} \\ & \end{align} In (\ref{1}), the sum is extended to $$\ds{\color{red}{\infty}}$$ because $$\ds{z^{k}\mbox{-power}}$$ with $$\ds{k > n}$$ does not give any contribution to the sum. That fact occurs due to the presence $$\ds{\mbox{of}~\bracks{z^{n}}}$$.

• Nice answer. (+1). You can differentiate ${\nu\choose n}$ using algebra by writing $$\left(\frac{1}{n!} \prod_{r=0}^{n-1} (\nu-r)\right)' = \frac{1}{n!} \prod_{r=0}^{n-1} (\nu-r) \sum_{r=0}^{n-1} \frac{1}{\nu-r}.$$ Then put $\nu=-1/2$ to get $-{-1/2\choose n} \times 2 \times \sum_{r=0}^{n-1} \frac{1}{2r+1}.$ Apr 25 at 20:10
• @MarkoRiedel Thanks. That happens because I'm a $\Gamma$-fan. I like your approach. I'll keep it for the future. Nice to see you again. Apr 25 at 22:58
• Thanks. And thanks for presenting Egorychev method on MSE, that was where I first learned it (posts by you and Markus Scheuer). Apr 25 at 23:03

We need to show that $$\sum\limits_{k=1}^n \frac{2^{2k-1}}{k} \binom{2(n-k)}{n-k} = \binom{2n}{n} \sum\limits_{k=1}^n \frac{1}{2k-1}$$

The generating function for the left hand side can be represented as a product:

$$\sum\limits_{n=1}^\infty \frac{1}{2}\sum\limits_{k=1}^n \left[\frac{2^{2k} x^k}{k} \right]\left[\binom{2(n-k)}{n-k}x^{n-k}\right] =\frac{1}{2}\left[\sum\limits_{k=1}^\infty \frac{2^{2k} x^k}{k}\right] \left[\sum\limits_{k=0}^\infty \binom{2k}{k} x^k\right]$$

The first factor evaluates to $$\log\frac{1}{1-4x}$$, and the second to $$\frac{1}{\sqrt{1-4x}}$$, thus

$$\boxed{G(x)=\frac{1}{\sqrt{1-4x}} \log \frac{1}{\sqrt{1-4x}}}$$

is the closed form expression for the generating function of the LHS.

Now, let's find the generating function for the right-hand side. Let

$$f_n = \binom{2n}{n} \sum\limits_{k=1}^n \frac{1}{2k-1},$$

then, taking into consideration $$\binom{2n}{n} = \frac{2(2n-1)}{n}\binom{2(n-1)}{n-1}$$, we can say that

$$f_n = \frac{2(2n-1)}{n}f_{n-1} + \frac{1}{2n-1}\binom{2n}{n}$$

with the base case $$f_0 = 0$$. Getting rid of denominators, that turns into

$$n(2n-1) f_n = 2(2n-1)^2 f_{n-1} + n \binom{2n}{n},$$

Let $$\Delta = x \frac{\partial}{\partial x}$$, then in terms of generating functions this rewrites as a diffeq:

$$\boxed{\Delta(2\Delta-1) F(x) = 2(2\Delta-1)^2 xF(x) + \Delta \frac{1}{\sqrt{1-4x}}}$$

In terms of just derivatives, it translates into

$$\boxed{2x(1 - 4x) F''(x) + (1-16x) F'(x) - 2F(x) = \frac{2}{(1-4x)^{3/2}}}$$

It admits a unique analytic solution subject to $$F(0)=f_0 = 0$$, and one can formally verify that $$G(x)$$ satisfies the differential equation.

Bonus: if you only know the equation, and you don't know the solution in advance, you can plug it into Wolfram and see that the general form of the solution here is

$$F(x) = \frac{1}{\sqrt{1-4x}}\left[c_1 + c_2 \arcsin(2\sqrt x) + \log\frac{1}{\sqrt{1-4x}}\right]$$