Waste less time on Facebook — follow Brilliant.
×

Binomial Coefficient Challenge 11!

Find a closed form of -

\[\large \displaystyle \sum_{k=1}^n{\binom{r}{k} {\left(-1\right)}^k H_k}\]

where \(H_k\) denotes \(k\)th Harmonic number.

Note by Kartik Sharma
1 month, 4 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Theorem : \[\sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r} = (-1)^m \dbinom{n-1}{m} \left( H_{m} + \dfrac{1}{n} \right) - \dfrac{1}{n}\]

Let,

\[ \text{S} = \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r} \]

From Binomial Coefficient Challenge 4, we have,

\[ \sum_{k=0}^{n-1} \dbinom{k}{r} \dfrac{1}{n-k} = \dbinom{n}{r} (H_{n} - H_{r}) \]

For \(r \geq 1\),

\[ \sum_{k=1}^{n-1} \dbinom{k}{r} \dfrac{1}{n-k} = \dbinom{n}{r} (H_{n} - H_{r}) \]

\[ \implies \sum_{k=1}^{n-1} \sum_{r=1}^{m} (-1)^r \dbinom{k}{r} \dfrac{1}{n-k} = H_{n} \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} - \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r} \]

\[ \implies \sum_{k=1}^{n-1} \left((-1)^m \dbinom{k-1}{m} - 1 \right)\dfrac{1}{n-k} = H_{n} \left[ (-1)^m \dbinom{n-1}{m} - 1 \right] - \text{S} \]

\[ \implies (-1)^m \sum_{k=0}^{n-2} \dbinom{k}{m} \dfrac{1}{n-k-1} - H_{n-1} = (-1)^m H_{n} \dbinom{n-1}{m} - H_{n} - \text{S} \]

\[ \implies \text{S} = (-1)^m \dbinom{n-1}{m} \left( H_{m} + \dfrac{1}{n} \right) - \dfrac{1}{n} \]

\[ \therefore \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r} = (-1)^m \dbinom{n-1}{m} \left( H_{m} + \dfrac{1}{n} \right) - \dfrac{1}{n} \quad \square \]

For \(m \geq n\), we see that the first term vanishes and we are left with the special case,

\[ \sum_{r=1}^{n} (-1)^r \dbinom{n}{r} H_{r} = - \dfrac{1}{n} \] Ishan Singh · 1 month, 4 weeks ago

Log in to reply

@Ishan Singh There is no typo. It is a finite sum and the answer should be valid for any \(r\) and \(n\). Kartik Sharma · 1 month, 4 weeks ago

Log in to reply

@Kartik Sharma I have answered for a general case. I have used \(n\) and \(m\) instead of \(r\) and \(n\). Btw, what's your approach? Ishan Singh · 1 month, 4 weeks ago

Log in to reply

If we define \[ a_n \; = \; \left\{ \begin{array}{lll} -\tfrac{1}{n} & \hspace{1cm} & n \ge 1 \\ 0 & & n = 0 \end{array}\right. \hspace{2cm} b_n \; = \; \left\{ \begin{array}{lll} H_n & \hspace{1cm} & n \ge 1 \\ 0 & & n = 0 \end{array} \right. \] then \[ H_n \; = \; -\sum_{k=1}^n \binom{n}{k} (-1)^k \frac{1}{k} \hspace{2cm} n \ge 1 \] so that \[ b_n \; = \; \sum_{k=0}^n \binom{n}{k} (-1)^k a_k \] and so, since we are using the Binomial Transform here, \[ a_n \; = \; \sum_{k=0}^n \binom{n}{k} (-1)^k b_k \] and hence \[ \sum_{k=1}^n \binom{n}{k}(-1)^k H_k \; = \; -\frac{1}{n} \hspace{2cm} n \ge 1 \] I presume that there is a slight typo in the question - \(\binom{n}{k}\) instead of \(\binom{r}{k}\). Of course, this makes no difference if \(n > r\). Mark Hennings · 1 month, 4 weeks ago

Log in to reply

@Mark Hennings There is no typo. It is a finite sum and the answer should be valid for any \(r\) and \(n\). Kartik Sharma · 1 month, 4 weeks ago

Log in to reply

@Mark Hennings Surprisingly, there is a general closed form too! I discovered it using challenge 4. BCC 4 is indeed an intriguing problem. Ishan Singh · 1 month, 4 weeks ago

Log in to reply

After some experience in finite calculus, it is not difficult to observe

\(\displaystyle \Delta\left({(-1)}^{k-1}\binom{r-1}{k-1}\right) = \binom{r-1}{k} {(-1)}^k - \binom{r-1}{k-1}{(-1)}^{k-1} = {(-1)}^k \binom{r}{k}\)

And we would be using SBP -

\[\displaystyle \sum {u(x) \Delta(v(x))} = u(x)v(x) - \sum {v(x+1) \Delta(u(x)}\]

Therefore, our finite sum -

\[\displaystyle \sum {\binom{r}{k}{(-1)}^k H_k \delta k}\]

\[\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k - \sum {\binom{r-1}{k}{(-1)}^k \frac{\delta k}{k+1}}\]

\[\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k - \frac{1}{r}\sum {\frac{r}{k+1}\binom{r-1}{k}{(-1)}^k \delta k}\]

\[\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k + \frac{1}{r}\sum {\binom{r}{k+1}{(-1)}^{k+1} \delta k}\]

Using our first difference in the sum form,

\[\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k + \frac{1}{r} {(-1)}^k\binom{r-1}{k}\]

Now using the limits \(1\) and \(n+1\),

\[\displaystyle = {(-1)}^{n}\binom{r-1}{n} H_{n+1} - \frac{1}{r} {(-1)}^n\binom{r-1}{n+1} - 1 + \frac{r-1}{r}\]

\[\displaystyle = {(-1)}^{n}\binom{r-1}{n} \left(H_n + \frac{1}{r}\right) - \frac{1}{r}\] Kartik Sharma · 1 month, 3 weeks ago

Log in to reply

@Ishan Singh @Mark Hennings Try not to use calculus approach. Kartik Sharma · 1 month, 4 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...