How to show the following? $$i^m-i(i-1)^m+\frac{i(i-1)}{1.2} (i-2)^m-...(-1)^{i-1}.i.1^m=0$$ (if $i>m$)
This seems really complicated.Can't spot any pattern as such :\ .Someone help me out!
P.S: I don't think the question means $i$ is iota here because it says $i>m$
On
Taken from this answer:
In this answer there are three proofs of $$ \begin{align} \sum_{j=k}^n(-1)^{j-k}\binom{n}{j}\binom{j}{k} &=\left\{\begin{array}{} 1&\text{if }n=k\\ 0&\text{otherwise} \end{array}\right.\\ &=[n=k] \end{align} $$ where $[\dots]$ are Iverson Brackets. Furthermore, $\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}$ $$ \sum_{k=0}^m\binom{n}{k}\,\stirtwo{m}{k}k!=n^m $$ where $\stirtwo{m}{k}$ are Stirling Numbers of the Second Kind. Therefore, $$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(x-k)^m &=\sum_{k=0}^n\sum_{j=0}^m(-1)^{k-j}\binom{n}{k}\binom{m}{j}x^{m-j}k^j\\ &=\sum_{k=0}^n\sum_{j=0}^m\sum_{i=0}^j(-1)^{k-j}\binom{n}{k}\binom{m}{j}x^{m-j}\binom{k}{i}\stirtwo{j}{i}i!\\ &=\sum_{j=0}^m\sum_{i=0}^j(-1)^{n-j}\binom{m}{j}x^{m-j}\,[n=i]\,\stirtwo{j}{i}i!\\ &=\sum_{j=0}^m(-1)^{n-j}\binom{m}{j}x^{m-j}\stirtwo{j}{n}n! \end{align} $$ If $m\lt n$, then either $\binom{m}{j}=0$ or $\stirtwo{j}{n}=0$. If $m=n$, the only non-zero term is $j=m$.
Setting $n=x=i$ gives $$ \begin{align} \sum_{k=0}^i(-1)^k\binom{i}{k}(i-k)^m=0 \end{align} $$ since $m\lt i$.
On
I suppôse that $m\geq 1$. Your sum seems to be $$S=\sum_{k=0}^{i} { i \choose k}(i-k)^m (-1)^k$$
Putting $i-k=j$, this becomes $$ S=(-1)^i \sum_{j=0}^{i} { i \choose j}(j)^m (-1)^j=(-1)^i T$$
We have $$\sum_{j=0}^i {i \choose j}(-1)^j x^j=(1-x)^i=P_i(x)$$ Let $\tau =x\frac{d}{dx}$. It is easy to see by induction that for $i>h$, we have $\tau^h(P_i)(x)=Q_h(x)(1-x)^{i-h}$ where $Q_h(x)$ is a polynomial. In particular, as $i>m$, we get that $\tau^m(P_i)(1)=0$. But $$\tau^m( \sum_{j=0}^i {i \choose j}(-1)^j x^j)=\sum_{j=0}^i {i \choose j}(-1)^j j^m x^j$$ and hence $T=0$ and we are done.
On
We give a combinatorial proof for the claim. It is contained in the following more general
$\mathbf{Theorem.}$ The number $s_{n,m}$ of surjective maps $f:[m]\rightarrow [n]$ is given by
$$s_{m,n}= n^m-{n\choose 1}(n-1)^m+{n\choose 2}(n-2)^m- \ldots +(-1)^n {n\choose n-1} 1^m. $$ In particular
$$ n!= \sum_{i=0}^n (-1)^i {n\choose i} (n-i)^n; $$
and if $n>m$ then $s_{n,m}=0$ (which is a proof of the original claim).
For an integer $k\geq 1$ let $[k]:=\{1,\ldots,k\}.$ Let $\Omega$ be the family of all maps $f:[m]\rightarrow [n],$ and let $A_j=\{f\in \Omega: f([m]) \subseteq [n]-\{j\}\},$ for $j=1,\ldots, n.$ A map $f\in \Omega$ is non-surjective if $f\in A_j$ for some $j.$ For $J\subseteq [n]$ we note $A_J:=\bigcap_{i\in J} A_j=\{f\in \Omega: f([m]) \subseteq [n]-J\}.$ We get : $f$ is surjective iff $f \in \Omega-\bigcup_{j=1}^n A_j.$ Thus the number of surjective maps is by inclusion-exclusion \begin{eqnarray*} |\Omega -\bigcup_{j=1}^n A_j|&=& |\Omega|-|\bigcup_{j=1}^n A_j|\\ &=& n^m - \sum_{i=1}^n (-1)^i \sum_{\scriptsize \begin{array}{c} I\subseteq [n] \\|I|=i \end{array}} |A_I| \\ & = & n^m- \sum_{i=1}^n (-1)^i \sum_{\scriptsize \begin{array}{c} I\subseteq [n] \\ |I|=i \end{array}} (n-|I|)^m = \sum_{i=0}^n (-1)^i {n\choose i} (n-i)^m. \end{eqnarray*} We thus get the first part. The second part is consequence of that the surjective functions from $[n]$ to $[n]$ are exactly the bijective ones; and of these there exist precisely $n!.$ Finally if $n>m$ there do not exist any surjective maps, so then $s_{n,m}=0.$ $\Box$
Theorem: For $n\gt m\ge0$, we have $$ \sum_{k=0}^n(-1)^k\binom{n}{k}k^m=0 $$ Proof: Suppose this holds for $n-1$, then $$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}k^m &=\sum_{k=0}^n(-1)^k\left[\binom{n-1}{k}+\binom{n-1}{k-1}\right]k^m\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{n-1}{k}k^m-\sum_{k=0}^{n-1}(-1)^k\binom{n-1}{k}(k+1)^m\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{n-1}{k}\left[k^m-(k+1)^m\right]\\ &=-\sum_{k=0}^{n-1}(-1)^k\binom{n-1}{k}\left[\sum_{j=0}^{m-1}\binom{m}{j}k^j\right]\\ &=-\sum_{j=0}^{m-1}\binom{m}{j}\color{#C00000}{\sum_{k=0}^{n-1}(-1)^k\binom{n-1}{k}k^j}\\ \end{align} $$ and each term in red is $0$ by the inductive hypothesis since $j\le m-1\lt n-1$. Therefore, the theorem holds for $n$.
All we need to show is that the theorem holds for $n=1$ and $m=0$, which is $1-1=0$.
QED
$$ \begin{align} \sum_{k=0}^i(-1)^k\binom{i}{k}(i-k)^m &=\sum_{k=0}^i(-1)^k\binom{i}{k}\sum_{j=0}^m(-1)^j\binom{m}{j}i^{m-j}k^j\\ &=\sum_{j=0}^m(-1)^j\binom{m}{j}i^{m-j}\color{#C00000}{\sum_{k=0}^i(-1)^k\binom{i}{k}k^j} \end{align} $$ where each term in red is $0$ by the Theorem since $j\le m\lt i$.