Question

Let n be a positive integer. Prove that $\sum _{k=0}^n(\frac{n}{k})(\frac{n+k}{k})=\sum _{k=0}^n{2}^k{(\frac{n}{k})}^2.$

• A. Adding on k, we obtain that the total number of pairs (A, B) equals $\sum _{k=0}^n{2}^k{(\frac{n}{k})}^2,$ hence the conclusion.
• B. Adding on k, we obtain that the total number of pairs (A, B) equals $\sum _{k=0}^n{2}^k{(\frac{n}{k})}^1,$ hence the conclusion.
• C. Adding on k, we obtain that the total number of pairs (A, B) equals $\sum _{k=0}^{n}2{(\frac{n}{k})}^2,$ hence the conclusion.
• D. Adding on k, we obtain that the total number of pairs (A, B) equals $\sum _{k=1}^n{2}^k(\frac{n}{k}),$ hence the conclusion.

Answer 1

The correct option is A Adding on k, we obtain that the total number of pairs (A, B) equals $\sum _{k=0}^n{2}^k{(\frac{n}{k})}^2,$ hence the conclusion.

Let us count in two ways the number of ordered pairs (A, B), Where A is a subset of $\{1,2,...,n\}$ and B is a subset of $\{1,2,...,2n\}$ with n elements and disjoint from A. First, for $0\le k\le n,$ choose a subset A of $\{1,2,...,n\}$ having $n-k$ elements. This can be done in $(\frac{n}{n-k})=(\frac{n}{k})$ ways. Next, choose B, a subset with n elements of $\{1,2,...,2n\}-A$
Since, $\{1,2,...,2n\}-A$ has $2n-(n-k)=n+k$ elements, B can be chosen in $(\frac{n+k}{n})=(\frac{n+k}{k})$ ways. We deduce, by adding on k, that the number of such pairs equals $\sum _{k=0}^n(\frac{n}{k})(\frac{n+k}{k}).$

On the other hand, we could start by choosing the subsets $B\{1,2,...,n\}$ and $B^{\prime \prime }\subset \{n+1,n+2,...,2n\},$ both with k elements, and define
$B=B^{\prime \prime }\cup (\{1,2,...,n\}-B^{\prime }).$ Since for given k each of the sets B' and B'' can be chosen in $(\frac{n}{k})$ ways, B can be chosen in ${(\frac{n}{k})}^2$ ways.

Finally, pick A to be an arbitrary subset of B'.

There are $2^k$ ways to do this. Adding on k, we obtain that the total number of pairs $(A,B)$ equals $\sum _{k=0}^n{2}^k{(\frac{n}{k})}^2$