Combination Summation problem

Question

I obtained $np/2$ which has a similar form as q but I'm unable to prove that it is equal to $q$.

Answer 1

As a first step, we have better to simplify and pass from the double sums to simple ones.

Let's put $$ s(n) = \sum\limits_{1\, \le \,k\, \le \,n} {\frac{1}{{\left( \begin{array}{c} n \\ k\\ \end{array} \right)}}} = \frac{1}{{n!}}\sum\limits_{1\, \le \,k\, \le \,n} {k!\left( {n - k} \right)!} $$ Then $$ \begin{array}{l} \sum\limits_{1\, \le \,k\, < \,j\, \le \,n} {\frac{1}{{\left( \begin{array}{c} n \\ k \\ \end{array} \right)}} + \frac{1}{{\left( \begin{array}{c} n \\ j \\ \end{array} \right)}}} + \sum\limits_{1\, \le \,j\, < \,k\, \le \,n} {\frac{1}{{\left( \begin{array}{c} n \\ k \\ \end{array} \right)}} + \frac{1}{{\left( \begin{array}{c} n \\ j \\ \end{array} \right)}}} + 2\sum\limits_{1\, \le \,k\, \le \,n} {\frac{1}{{\left( \begin{array}{c} n \\ k \\ \end{array} \right)}}} = \\ = 2p(n) + 2s(n) = \\ = \sum\limits_{\begin{array}{*{20}c} {1\, \le \,k\, \le \,n} \\ {1\, \le \,j\, \le \,n} \\ \end{array}} {\left( {\frac{1}{{\left( \begin{array}{c} n \\ k \\ \end{array} \right)}} + \frac{1}{{\left( \begin{array}{c} n \\ j \\ \end{array} \right)}}} \right)} = \sum\limits_{1\, \le \,k\, \le \,n} {\sum\limits_{1\, \le \,j\, \le \,n} {\left( {\frac{1}{{\left( \begin{array}{c} n \\ k \\ \end{array} \right)}} + \frac{1}{{\left( \begin{array}{c} n \\ j \\ \end{array} \right)}}} \right)} } = \\ = \sum\limits_{1\, \le \,k\, \le \,n} {\left( {\frac{n}{{\left( \begin{array}{c} n \\ k \\ \end{array} \right)}} + s(n)} \right)} = 2n\,s(n)\quad \Rightarrow \\ \Rightarrow \quad p(n) = \left( {n - 1} \right)\,s(n) \\ \end{array} $$

Similarly, putting $$ r(n) = \sum\limits_{1\, \le \,k\, \le \,n} {{k \over {\binom{n}{k}}}} $$ we get $$ \eqalign{ & \sum\limits_{1\, \le \,k\, < \,j\, \le \,n} { {k \over {\binom {n}{k}}} + {j \over {\binom {n}{j}}}} + \sum\limits_{1\, \le \,j\, < \,k\, \le \,n} {{k \over {\binom {n}{k}}} + {j \over {\binom {n}{j}}}} + 2\sum\limits_{1\, \le \,k\, \le \,n} {{k \over {\binom {n}{k}}}} = \cr & = 2q(n) + 2r(n) = \cr & = \sum\limits_{\matrix{ {1\, \le \,k\, \le \,n} \cr {1\, \le \,j\, \le \,n} \cr } } {\left( {{k \over {\binom {n}{k}}} + {j \over {\binom {n}{j}}}} \right)} = \sum\limits_{1\, \le \,k\, \le \,n} {\sum\limits_{1\, \le \,j\, \le \,n} { \left( {{k \over {\binom {n}{k}}} + {j \over {\binom {n}{j}}}} \right)} } = \cr & = \sum\limits_{1\, \le \,k\, \le \,n} {\left( {n{k \over {\binom {n}{k}}} + q(n)} \right)} = 2n\,r(n) \quad \Rightarrow \cr & \Rightarrow \quad q(n) = \left( {n - 1} \right)\,r(n) \cr} $$

We can then work on $s(n),\, r(n)$ to obtain $$ \eqalign{ & r(n) + s(n) = \sum\limits_{1\, \le \,k\, \le \,n} {{{k + 1} \over {\binom{n}{k}}}} = \cr & = {1 \over {n!}}\sum\limits_{1\, \le \,k\, \le \,n} {\left( {k + 1} \right)!\left( {n - k} \right)!} = \cr & = \left( {n + 1} \right)\left( {{1 \over {\left( {n + 1} \right)!}}\sum\limits_{1\, \le \,k\, \le \,n} {\left( {k + 1} \right)!\left( {n + 1 - \left( {k + 1} \right)} \right)!} } \right) = \cr & = \left( {n + 1} \right)\left( {{1 \over {\left( {n + 1} \right)!}}\sum\limits_{2\, \le \,k\, \le \,n + 1} {k!\left( {n + 1 - k} \right)!} } \right) = \cr & = \left( {n + 1} \right)\left( {s(n + 1) - {{n!} \over {\left( {n + 1} \right)!}}} \right) = \left( {n + 1} \right)s(n + 1) - 1 \cr} $$

and $$ \eqalign{ & s(n + 1) = \sum\limits_{1\, \le \,k\, \le \,n + 1} {{1 \over {\left( \matrix{ n + 1 \cr k \cr} \right)}}} = \cr & = {1 \over {\left( {n + 1} \right)!}}\sum\limits_{1\, \le \,k\, \le \,n + 1} {k!\left( {n + 1 - k} \right)!} = \cr & = {1 \over {\left( {n + 1} \right)!}}\left( {\sum\limits_{1\, \le \,k\, \le \,n} {k!\left( {n + 1 - k} \right)!} + \left( {n + 1} \right)!} \right) = \cr & = 1 + {1 \over {\left( {n + 1} \right)!}}\sum\limits_{1\, \le \,k\, \le \,n} {\left( {n + 1 - k} \right)k!\left( {n - k} \right)!} = \cr & = 1 + {1 \over {\left( {n + 1} \right)!}}\left( {\left( {n + 2} \right)\sum\limits_{1\, \le \,k\, \le \,n} {k!\left( {n - k} \right)!} - \sum\limits_{1\, \le \,k\, \le \,n} {\left( {k + 1} \right)!\left( {n + 1 - \left( {k + 1} \right)} \right)!} } \right) = \cr & = 1 + {1 \over {\left( {n + 1} \right)!}}\left( {\left( {n + 2} \right)n!s(n) - \sum\limits_{1\, \le \,k\, \le \,n} {\left( {k + 1} \right)!\left( {n + 1 - \left( {k + 1} \right)} \right)!} } \right) = \cr & = 1 + {1 \over {\left( {n + 1} \right)!}}\left( {\left( {n + 2} \right)n!s(n) - \sum\limits_{2\, \le \,k\, \le \,n + 1} {k!\left( {n + 1 - k} \right)!} } \right) = \cr & = 1 + {1 \over {\left( {n + 1} \right)!}}\left( {\left( {n + 2} \right)n!s(n) - \left( {n + 1} \right)!s(n + 1) + n!} \right) = \cr & = 1 + {{n + 2} \over {n + 1}}s(n) - s(n + 1) + {1 \over {n + 1}}\quad \Rightarrow \cr & \Rightarrow \quad s(n + 1) = {{n + 2} \over {2\left( {n + 1} \right)}}\left( {1 + s(n)} \right) \cr} $$ So, the final result is $$ \bbox[lightyellow] { \left\{ \matrix{ p(n) = \left( {n - 1} \right)\,s(n) \hfill \cr q(n) = \left( {n - 1} \right)\,r(n) \hfill \cr r(n) + s(n) = \left( {n + 1} \right)s(n + 1) - 1 \hfill \cr s(n + 1) = {{n + 2} \over {2\left( {n + 1} \right)}}\left( {1 + s(n)} \right) \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ r(n) = {n \over 2}\left( {s(n) + 1} \right) \hfill \cr p(n) = \left( {n - 1} \right)\,s(n) \hfill \cr q(n) = {n \over 2}\left( {p(n) + \left( {n - 1} \right)} \right) \hfill \cr} \right. }$$ which is not as expected.

In fact, you should define the sums to start from zero $$ \bbox[lightyellow] { \eqalign{ & \matrix{ \matrix{ p^ * (n) = \sum\limits_{0\, \le \,k\, < \,j\, \le \,n} {{1 \over { \binom{n}{k} }} + {1 \over { \binom{n}{j} }}} = \hfill \cr = \sum\limits_{0\, < \,j\, \le \,n} {\left( {1 + {1 \over {\binom{n}{j}}}} \right)} + \sum\limits_{1\, \le \,k\, < \,j\, \le \,n} {{k \over {\binom{n}{k} }} + {j \over {\binom{n}{j}}}} = \hfill \cr = n + s(n) + p(n) \hfill \cr} & {\;\;\;} & \matrix{ q^ * (n) = \sum\limits_{0\, \le \,k\, < \,j\, \le \,n} {{k \over {\binom{n}{k} }} + {j \over {\binom{n}{j}}}} = \hfill \cr = \sum\limits_{0\, < \,j\, \le \,n} {\left( {{j \over {\binom{n}{j}}}} \right)} + \sum\limits_{1\, \le \,k\, < \,j\, \le \,n} {{k \over {\binom{n}{k}}} + {j \over {\binom{n}{j}}}} = \hfill \cr = r(n) + q(n) \hfill \cr} \cr } \cr & \cr} }$$ to obtain $$ \bbox[lightyellow] { q^ * (n) = {n \over 2}p^ * (n) }$$