Heergerneuu
2022-09-26
Answered

Proof of a combination identity: $\sum _{j=0}^{n}(-1{)}^{j}{\textstyle (}\genfrac{}{}{0ex}{}{n}{j}{\textstyle )}{(1-\frac{j}{n})}^{n}=\frac{n!}{{n}^{n}}$

You can still ask an expert for help

Kaiden Stevens

Answered 2022-09-27
Author has **12** answers

Start with

$$\sum _{j=0}^{n}(-1{)}^{j}{\textstyle (}\genfrac{}{}{0ex}{}{n}{j}{\textstyle )}(1+x{)}^{n-j}={x}^{n}$$

which follows readily from the binomial theorem.

Now differentiate, and multiply by $(1+x)$. Repeat this $n$ times and set $x=0$.

Notice that the constant term of the resulting polynomial on the right side is $n!$.

You can prove by induction that the lowest degree of $x$ that appears on the right side after $k$ steps $0<{\displaystyle k\le n}$ is $x}^{n-k$ and has the coefficient $n(n-1)\dots (n-k+1)$.

This gives us the set of identities

$$\sum _{j=0}^{n}(-1{)}^{j}{\textstyle (}\genfrac{}{}{0ex}{}{n}{j}{\textstyle )}(n-j{)}^{k}=0,\text{}\text{}0\le kn$$

$$\sum _{j=0}^{n}(-1{)}^{j}{\textstyle (}\genfrac{}{}{0ex}{}{n}{j}{\textstyle )}(n-j{)}^{n}=n!$$

$$\sum _{j=0}^{n}(-1{)}^{j}{\textstyle (}\genfrac{}{}{0ex}{}{n}{j}{\textstyle )}(1+x{)}^{n-j}={x}^{n}$$

which follows readily from the binomial theorem.

Now differentiate, and multiply by $(1+x)$. Repeat this $n$ times and set $x=0$.

Notice that the constant term of the resulting polynomial on the right side is $n!$.

You can prove by induction that the lowest degree of $x$ that appears on the right side after $k$ steps $0<{\displaystyle k\le n}$ is $x}^{n-k$ and has the coefficient $n(n-1)\dots (n-k+1)$.

This gives us the set of identities

$$\sum _{j=0}^{n}(-1{)}^{j}{\textstyle (}\genfrac{}{}{0ex}{}{n}{j}{\textstyle )}(n-j{)}^{k}=0,\text{}\text{}0\le kn$$

$$\sum _{j=0}^{n}(-1{)}^{j}{\textstyle (}\genfrac{}{}{0ex}{}{n}{j}{\textstyle )}(n-j{)}^{n}=n!$$

furajat4h

Answered 2022-09-28
Author has **1** answers

Lemma: Let $f(j)=\sum _{k=0}^{n}{f}_{k}{j}^{k}$ be a degree $n$ polynomial. Claim that $\sum _{j=0}^{n}(-1{)}^{j}{\textstyle (}\genfrac{}{}{0ex}{}{n}{j}{\textstyle )}f(j)=n!{f}_{n}$.

Proof: For any polynomial $g$, define $\mathrm{\Delta}(g)$ to be the polynomial $\mathrm{\Delta}(g)$$\mathrm{\Delta}(g)(j)=g(j)-g(j+1)$. Observe that, if $g$ is a polynomial with leading term $a{x}^{d}+\cdots $, then $\mathrm{\Delta}(g)$ is a polynomial with leading term $-da{x}^{d-1}+\cdots $. In particular, if $f$ is as in the statement of the lemma, then ${\mathrm{\Delta}}^{n}(f)$ is the constant $(-1{)}^{n}n!{f}_{n}$. The sum in question is ${\mathrm{\Delta}}^{n}(f)$ evaluated at $0$. QED

Now, apply the lemma to $f(j)=(1-j/n{)}^{n}$.

Proof: For any polynomial $g$, define $\mathrm{\Delta}(g)$ to be the polynomial $\mathrm{\Delta}(g)$$\mathrm{\Delta}(g)(j)=g(j)-g(j+1)$. Observe that, if $g$ is a polynomial with leading term $a{x}^{d}+\cdots $, then $\mathrm{\Delta}(g)$ is a polynomial with leading term $-da{x}^{d-1}+\cdots $. In particular, if $f$ is as in the statement of the lemma, then ${\mathrm{\Delta}}^{n}(f)$ is the constant $(-1{)}^{n}n!{f}_{n}$. The sum in question is ${\mathrm{\Delta}}^{n}(f)$ evaluated at $0$. QED

Now, apply the lemma to $f(j)=(1-j/n{)}^{n}$.

asked 2021-09-08

A restaurant offers a $12 dinner special with seven appetizer options, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?

asked 2021-09-09

In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?

asked 2022-05-16

Factorial is defined as

$n!=n(n-1)(n-2)\cdots 1$

But why mathematicians named this thing as factorial?

$n!=n(n-1)(n-2)\cdots 1$

But why mathematicians named this thing as factorial?

asked 2022-02-23

A statistic instructor ( with at least 20 years of teaching experience with the same course) has established that 10 percent of all students who take his course receive a failing grade. If 10 students have enrolled in his course for the next semester, the probability that **more than one ** of these students will fail is

asked 2020-12-13

A radio station gives a pair of concert tickets to the six caller who knows the birthday of the performer. For each person who calls, the probability is 0.75 of knowing the performers

asked 2020-10-27

With one score eliminated from the population, the new mean is discovered to be $\mu =19$, which corresponds to a population of N = 16 scores with a mean of p = 20. What was the significance of the removed in-e score?

asked 2021-06-24