3

Show that the number:

$$7^n-\binom71\cdot 6^n+\binom72\cdot5^n-\binom73\cdot4^n+\binom74\cdot3^n-\binom75\cdot2^n+\binom76$$

is divisible by $7!$ for every $n\in \mathbb{N}$

Tried to do it by induction but the binomial coefficient confuses me

Thanks in advance!

Community
  • 1
user21312
  • 966
  • I get $0$ for the sum when $n=2$. Indeed it is $49 - 252+525-560 +315-84+7$ The positives add to $49+525+315+7=896$ and the negatives add to $252+560+84=896$. More generally, the sum can be thought of as the number of ways to distribute $n$ objects to $7$ people such that each person gets at least $1$. – lulu Mar 23 '17 at 16:45
  • 1
    see this post http://math.stackexchange.com/questions/1642204/factorial-summation-definition/1642263#1642263 – René Gy Mar 23 '17 at 22:21

1 Answers1

1

Here is an alternate approach to induction, based upon the coefficient of operator $[z^k]$. It used to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} [z^j](1+z)^k=\binom{k}{j}\qquad\qquad\text{or}\qquad\qquad k![z^k]e^{jz}=j^k \end{align*}

We obtain \begin{align*} 7^n&-\binom{7}{1}\cdot 6^n+\binom{7}{2}\cdot5^n-\binom{7}{3}\cdot4^n+\binom{7}{4}\cdot3^n-\binom{7}{5}\cdot2^n+\binom{7}{6}\\ &=\sum_{j=0}^7\binom{7}{j}(7-j)^n(-1)^j\tag{1}\\ &=\sum_{j=0}^7\binom{7}{j}j^n(-1)^{7-j}\tag{2}\\ &=(-1)^7\sum_{j=0}^\infty[z^j](1+z)^7n![u^n]e^{-ju}(-1)^{j}\tag{3}\\ &=(-1)^7n![u^n]\sum_{j=0}^\infty \left(-e^u\right)^j[z^j](1+z)^7\tag{4}\\ &=(-1)^7n![u^n](1-e^u)^7\tag{5}\\ &=7!n![u^n]\frac{(e^u-1)^7}{7!}\tag{6}\\ &=7!{n\brace 7} \end{align*} with ${n\brace 7}$ the Stirling numbers of the second kind.

Since the Stirling numbers of the second kind are non-negative integers and they are multiplied with $7!$, the claim follows.

Comment:

  • In (1) we use the summation symbol to write the expression more compactly.

  • In (2) we change the order of summation by replacing $j \rightarrow 7-j$.

  • In (3) we apply the coefficient of operator twice and extend the upper limit of the sum to $\infty$ without changing anything since we are adding zeros only.

  • In (4) we do some rearrangements as preparation for the next step.

  • In (5) we apply the substitution rule of the coefficient of operator with $z:=-e^u$ \begin{align*} A(u)=\sum_{k=0}^\infty a_k u^k=\sum_{k=0}^\infty u^k [z^k]A(z) \end{align*}

  • In (6) we do a small rearrangement and observe we obtain an exponential generating function of ${n\brace k}$, the Stirling numbers of the second kind.

Markus Scheuer
  • 108,315