9
$\begingroup$

If $$f(x)=\binom{n}{1}(x-1)^2-\binom{n}{2}(x-2)^2+\cdots+(-1)^{n-1}\binom{n}{n}(x-n)^2$$ Find the value of $$\int_0^1f(x)dx$$

I rewrote this into a compact form. $$\sum_{k=1}^n\binom{n}{k}(x-k)^2(-1)^{k-1}$$ Now, $$\int_0^1\sum_{k=1}^n\binom{n}{k}(x-k)^2(-1)^{k-1}dx$$ $$=\sum_{k=1}^n\binom{n}{k}\frac{(1-k)^3}{3}(-1)^{k-1}-\sum_{k=1}^n\binom{n}{k}\frac{(-k)^3}{3}(-1)^{k-1}$$ $$=\sum_{k=1}^n\binom{n}{k}\frac{(1-k)^3}{3}(-1)^{k-1}+\sum_{k=1}^n\binom{n}{k}\frac{k^3}{3}(-1)^{k-1}$$ After this, I took $\dfrac13$ common and did some simplifications but nothing useful came out.

Any help is greatly appreciated.

$\endgroup$
6
  • $\begingroup$ What make you think there is a closed-form formula ? $\endgroup$
    – Jean Marie
    Dec 16, 2022 at 17:36
  • 1
    $\begingroup$ What is $n$ equal to? $\endgroup$ Dec 16, 2022 at 17:40
  • $\begingroup$ Why not $\int_1^2 x^2 dx=\frac73$? $\endgroup$ Dec 16, 2022 at 17:43
  • $\begingroup$ What you want is a linear combination of $\displaystyle \sum_{r=\color{red}1}^n \binom nk (-1)^{k-1}k^r$, where $r=0,1,2$. Note that $\displaystyle \sum_{r=\color{red}{0}}^n \binom nk (-1)^{k-1}k^r=0.$ $\endgroup$ Dec 16, 2022 at 17:55
  • $\begingroup$ @TymaGaidash That WolframAlpha output is clearly not valid for $n=1$ or $n=2$. Btw. your link rendered as something that looks completely unrelated to the problem. $\endgroup$ Dec 16, 2022 at 17:57

5 Answers 5

9
$\begingroup$

A devious little problem indeed! I am interested in where you found it. We in fact have a very nice formula:

$$\sum_{k=1}^n (-1)^{k-1} \binom{n}{k} (x-k)^2 =x^2$$

It follows from:

$$F(x)=\sum_{k=1}^n (-1)^{k-1} \binom{n}{k} (x-k)^2 \\ =\sum_{k=1}^n (-1)^{k-1}\binom{n}{k}\big(x^2-2kx+k^2\big) \\ =x^2\color{red}{\sum_{k=1}^n (-1)^{k-1}\binom{n}{k}}-2x\color{green}{\sum_{k=1}^n (-1)^{k-1}\binom{n}{k}k}+\color{blue}{\sum_{k=1}^n (-1)^{k-1}\binom{n}{k}k^2}$$ Now, we need to somehow show

$$\color{red}{\blacksquare}=1 \\ \color{green}{\blacksquare}=\color{blue}{\blacksquare}=0$$

These sums have been studied before:

$\color{red}{\blacksquare}$ : Alternating sum of binomial coefficients equal to $1$

Follows from doing a binomial expansion of $(1-1)^n$.

$\color{green}{\blacksquare}$ : Binomial coefficient series $\sum\limits_{k=1}^n (-1)^{k+1} k \binom nk=0$

Follows from the recurrence $k\binom{n}{k}=n\binom{n-1}{k-1}$.

$\color{blue}{\blacksquare}$ : This is the hard one. We proceed as follows:

$$\sum_{k=1}^n (-1)^{k-1}k^2\binom{n}{k}=n\sum_{k=1}^n (-1)^{k-1}k \binom{n-1}{k-1} \tag{1}$$ $$ =n\sum_{l=0}^{n-1}(-1)^l(l+1)\binom{n-1}{l} \\ =n\sum_{l=0}^{n-1}(-1)^l l\binom{n-1}{l}+n\underbrace{\sum_{l=0}^{n-1}(-1)^l \binom{n-1}{l}}_{=(1-1)^{n-1}=0} $$ Finally, since $\binom{n-1}{n}=0$, and since the $l=0$ summand is zero, we can remove the $l=0$ index and add a $l=n$ index, and then rename the index back to $k$: $$n\sum_{l=0}^{n-1}(-1)^l l\binom{n-1}{l}=n\sum_{k=1}^n(-1)^k k\binom{n-1}{k}$$ Now, using the recurrence relation for the binomials, $$n\sum_{k=1}^n(-1)^k k\binom{n-1}{k}=n\underbrace{\sum_{k=1}^n k(-1)^k \binom{n}{k}}_{=\color{green}{\blacksquare}=0}-n\sum_{k=1}^n (-1)^kk \binom{n-1}{k-1}$$ Again, $k\binom{n-1}{k-1}=k^2\binom{n}{k}$ and hence $$-n\sum_{k=1}^n (-1)^kk \binom{n-1}{k-1}=-n\sum_{k=1}^n (-1)^kk^2 \binom{n}{k}=n\sum_{k=1}^n (-1)^{k-1}k^2 \binom{n}{k}\tag{2}$$ But, retracing our steps from $(1)$ to $(2)$, we have just proved that $$\sum_{k=1}^n (-1)^{k-1}k^2\binom{n}{k}=~\boldsymbol{n}~\sum_{k=1}^n (-1)^{k-1}k^2\binom{n}{k}$$

This can only be true for general $n$ if the sum is zero. Hence,

$$\boxed{\sum_{k=1}^n (-1)^{k-1} \binom{n}{k} (x-k)^2=x^2\color{red}{\blacksquare}-2x\color{green}{\blacksquare}+\color{blue}{\blacksquare} \\ =x^2}$$

QED!!

$\endgroup$
6
  • $\begingroup$ And of course, if follows $\int_0^1 f(x)\mathrm dx=\int_0^1 x^2\mathrm dx=\frac{1}{3}$. $\endgroup$
    – K.defaoite
    Dec 16, 2022 at 18:36
  • $\begingroup$ Also of importance - the formula breaks down for $n=0,1,2$, which should be clear enough from the methods used. $\endgroup$
    – K.defaoite
    Dec 16, 2022 at 18:37
  • $\begingroup$ This is too good. This was asked in a practice test....but you know these problems are meant to be left. $\endgroup$
    – user1131589
    Dec 16, 2022 at 18:44
  • $\begingroup$ Can you explain after the line "now using the recurrence relations... $\endgroup$
    – user1131589
    Dec 16, 2022 at 19:13
  • $\begingroup$ Vanessa, I used $\binom{n-1}{k}=\binom{n}{k}-\binom{n-1}{k-1}$. $\endgroup$
    – K.defaoite
    Dec 16, 2022 at 19:39
7
$\begingroup$

Solution 1. Here is another approach. Consider the shift operator $\Delta$ defined for functions on $\mathbb{R}$ by

$$ \Delta f(x) = f(x-1). $$

Then

\begin{align*} \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} (x-k)^2 &= \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \Delta^k x^2 \\ &= [\operatorname{id} - (\operatorname{id} - \Delta)^n] x^2. \end{align*}

Here, $\operatorname{id}$ is the identity operator on functions, i.e., $\operatorname{id} f(x) = f(x)$. Now the crucial observation is as follows:

The backward difference operator $D = \operatorname{id} - \Delta$, when applied to a polynomial, results in another polynomial with degree decreased by at least one.

Intuitively, this is because $D$ behaves similar to the differential operator $\frac{\mathrm{d}}{\mathrm{d}x}$. In particular, when $n \geq 3$, it follows that $D^n x^2 = 0$. Hence it follows that

$$ \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} (x-k)^2 = x^2 \qquad\text{for}\quad n \geq 3. $$

Now the rest computation is straightforward.


Solution 2. Here is yet another approach. Define the coefficient extraction operator $[x^n]$ by

$$ [x^n]\sum_{k=0}^{\infty} a_k x^k = a_k. $$

Note that $[x^n]$ is linear. Furthermore, we may rewrite the integral using this operator as:

\begin{align*} \int_{0}^{1} f(x) \, \mathrm{d}x &= \int_{0}^{1} \left( \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} (x-k)^2 \right) \, \mathrm{d}x \\ &= \int_{0}^{1} \left( \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} 2 [s^2] e^{(x-k)s} \right) \, \mathrm{d}x \\ &= 2 [s^2] \int_{0}^{1} \left( \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} e^{(x-k)s} \right) \, \mathrm{d}x \\ &= 2 [s^2] \int_{0}^{1} e^{xs} \left( 1 - (1 - e^{-s})^n \right) \, \mathrm{d}x \\ &= 2 [s^2] \left( \frac{e^s - 1}{s} \left( 1 - (1 - e^{-s})^n \right) \right). \end{align*}

Then, using the fact that

$$ \frac{e^s - 1}{s} = 1 + \frac{s}{2} + \frac{s^2}{6} + \mathcal{O}(s^3) $$

and

$$ 1-(1-e^{-s})^n = \begin{cases} 1 - s + \frac{s^2}{2} + \mathcal{O}(s^3), & n = 1, \\ 1 - s^2 + \mathcal{O}(s^3), & n =2, \\ 1 + \mathcal{O}(s^3), & n \geq 3, \end{cases} $$

we can easily conclude that

$$ \int_{0}^{1} f(x) \, \mathrm{d}x = \begin{cases} \frac{1}{3}, & n = 1 \text{ or } n \geq 3, \\ -\frac{5}{3}, & n = 2. \end{cases} $$

$\endgroup$
3
  • $\begingroup$ What is $e?$ Is it the famous irrational number$?$ And what is $s?$ And is that the big-o notation $?$ $\endgroup$
    – user1131589
    Dec 16, 2022 at 19:03
  • $\begingroup$ @Vanessa2.0 $e^x = \exp(x)$ stands for the natural exponential function. Also, $s$ is just an auxiliary variable that is introduced so as to realize each $(x-k)^2$ as a coefficient of some power series. Finally, $\mathcal{O}(s^3)$ is the big-O notation, but you may simply regard them as generic power series whose $0$th, $1$st, and $2$nd coefficients all vanish (and that never affects the value of the coefficient of $s^2$ in the computation). $\endgroup$ Dec 16, 2022 at 19:06
  • 2
    $\begingroup$ Genius! I love this answer and how you handled the $n=1,2$ cases. $\endgroup$
    – K.defaoite
    Dec 16, 2022 at 19:42
2
$\begingroup$

Hint:

Another way:

$$f(x)=\sum_{k=1}^n\binom nk(x-k)^2(-1)^{k+1}$$

$(x-k)^2=x^2+k(1-2x)+k(k-1)$

$$\binom nk(x-k)^2=x^2\binom nk+(1-2x)n\binom{n-1}{k-1}+n(n-1)\binom{n-2}{k-2}$$

$$\sum_{k=1}^n(-1)^{k+1}\binom nk=-\sum_{k=1}^n\binom nk(-1)^k=1-(1-1)^n$$

$$\sum_{k=1}^n(-1)^{k+1}\binom{n-1}{k-1}=\sum_{k=1}^n\binom{n-1}{k-1}(-1)^{k-1}=(1-1)^{n-1}=?$$

$$\sum_{k=1}^n(-1)^{k+1}\binom{n-2}{k-2}=?$$

$\endgroup$
1
  • $\begingroup$ The answer given to this question was $\dfrac13$. I'm not able to transform the last expression into that constant value. Please help. $\endgroup$
    – user1131589
    Dec 16, 2022 at 18:10
1
$\begingroup$

We consider the more general function

$$f(x,m,n) =\sum _{k=1}^n (-1)^{k-1} \binom{n}{k} (x-k)^m\tag{1}$$

with $m=0,1,2,...$ and $n\ge 1$. The case of interest here has $m=2$.

It turns out (*) that $f(x,m,n\ge m+1) = x^m$ so that the integral becomes in this case

$$i(m,n\ge m+1) = \int_{0}^{1} f(x,m,n\ge m+1)\;dx = \frac {1}{m+1}\tag{2}$$

For any $n\ge 1$, including $n \le m$, we do the $x$-integral and obtain for the integral in question this expression

$$i(m,n) = \frac{1}{m+1}i_1 (m,n)\tag{3a}$$

where the numerator is

$$i_1 (m,n) = \sum _{k=1}^n (-1)^{k-1} \binom{n}{k}\left(k (-k)^m+(1-k)^{m+1}\right)\tag {3b}$$

For $m=2$ we get

$$i(2,1) = \frac{1}{3}\\ i(2,2) = -\frac{5}{3}\\ i(2,n\ge 3) = \frac{1}{3} $$

In general the start of the matrix of the numerator $i_1(m,n)$ reads

$$i_1(m,n)=\left( \begin{array}{cccccc} 1 & 1 & 1 & 1 & 1 & 1 \\ -1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -5 & 1 & 1 & 1 & 1 \\ -1 & 13 & -23 & 1 & 1 & 1 \\ 1 & -29 & 121 & -119 & 1 & 1 \\ -1 & 61 & -479 & 1081 & -719 & 1 \\ \end{array} \right)\tag{4}$$

The second column of this matrix in listed in OEIS as http://oeis.org/A036563, the third and forthcoming columns are not contained in OEIS.

Notice that appearantly

$$i_1(m, n\ge m+1) = 1\tag{*}$$

In other words, if there are sufficiently many summands in $i_1$ ($n \ge m+1$) all terms add up to unity.

Unfortunately, I haven't yet found a prrof for (*).

A possibly useful intermediate result is the generating function of $h_1$ with respect to $m$:

Replacing the kernel

$$\sum _{m=0}^{\infty } \left(k (-k)^m+(1-k)^{m+1}\right) t^m=\frac{1}{(k t+1) (k t-t+1)}$$

in $i_1$ we obtain

$$g_1(t,n) := \sum _{m=0}^{\infty } t^m i_1(m,n) \\ = \sum _{k=1}^n \frac{(-1)^{k-1} \binom{n}{k}}{(k t+1) (k t-t+1)}\\= \frac{\Gamma (n+2) \Gamma \left(\frac{t+1}{t}\right)}{(t-1) \Gamma \left(\frac{n t+t+1}{t}\right)}-\frac{1}{t-1}\\ =\frac{1}{t-1}\left(\frac{\Gamma (n+2) \Gamma \left(\frac{1}{t}+1\right)}{ \Gamma \left(\frac{1}{t}+n+1\right)}-1 \right) \tag{5}$$

(proof of (*) still to be done)

$\endgroup$
1
$\begingroup$

We wish to evaluate the sum $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(x-k)^2=x^2-\sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}(x-k)^2.$$

Consider an $x\times x$ board, where $x\ge n$ is an integer, in which we want to choose a single square, and the list of properties $\Omega=\{P_i\mid i=0,\dots,n\}$, where the property $P_i$ is "the $i$th row and the $i$th column of the square are empty".

Let $S\subseteq[n]=\{1,\dots,n\}$, then the number of ways to choose a single square on the board that satisfies the list of properties in $S$ is $$N(\supseteq S)=(x-|S|)^2.$$

There are $\binom{n}{k}$ sets $S\in[n]$, so $$N_k=\sum_{S\,:\,|S|=k}N(\supseteq S)=\binom{n}{k}(x-k)^2.$$

Therefore, by the Inclusion-Exclusion Principle, the number of $x\times x$ boards that satisfy none of the properties in $\Omega$ is $$ e_0(n,x)=\sum_{k=0}^{n}(-1)^k N_k=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(x-k)^2, $$ exactly the sum we want to evaluate. But any choice of a single square is a choice of 1 row and 1 column, so at most 2 such properties can be violated at the same time. Thus, we have the following.

If $n\ge 3$, then $e_0(x,n)=0$.

If $n=2$, there are $2$ such choices: (row 1, column 2) and (row 2, column 1), so $e_0(x,2)=2$.

If $n=1$, there are $2x-1$ such choices, since the chosen square must be in row 1 or column 1, so $e_0(x,1)=2x-1$.

If $n=0$, there are $0$ such choices, since the board is empty and we need to choose 1 square, so $e_0(x,0)=0$.

Finally, these formulas apply for any integer $x\ge n$, and since $e_0(x,n)$ is a polynomial in $x$, they must hold identically.

This can easily be generalized in various ways. For example, $$ \sum_{k=0}^{n}(-1)^k\binom{n}{k}(x-k)^m= \begin{cases} m!\,, & \text{ if } n=m,\\ 0\,, & \text{ if } n>m. \end{cases} $$

$\endgroup$

You must log in to answer this question.