induction regarding the binomial coefficient

Question

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!

Answer 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^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.