9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Cyankite
    Apr 24 at 4:48
  • $\begingroup$ Yes, if there's an algebraic proof, it may be more fascinating because it doesn't care about the background $\endgroup$
    – madala
    Apr 24 at 4:56

3 Answers 3

7
$\begingroup$

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

(previous:) I simplified your expression

$$\begin{equation} \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} \end{equation} $$ 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.

$\endgroup$
1
  • 1
    $\begingroup$ The proof is so brilliant and wonderful ! Thanks. Wish you good luck. $\endgroup$
    – madala
    Apr 25 at 3:55
4
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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}.$ $\endgroup$ Apr 25 at 20:10
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 25 at 22:58
  • 1
    $\begingroup$ Thanks. And thanks for presenting Egorychev method on MSE, that was where I first learned it (posts by you and Markus Scheuer). $\endgroup$ Apr 25 at 23:03
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .