If $P(x)$ is any polynomial of degree less than $n$, show that $\sum_{j=0}^n (-1)^j\binom{n}{j}P(j)=0$. 
If $P(x)$ is any polynomial of degree less than $n$, then prove that
$$\sum_{j=0}^n (-1)^j\binom{n}{j}P(j)=0$$

My approach was to try and prove this separately for $j^k\ \ \forall\ \ k<n$, instead of $P(j)$, since $P(x)$ can be written as $a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_0$. However, I could not get anywhere.It would be much appreciated if someone could provide a rigorous solution for this or any key insights.Thanks a lot
 A: We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$. This way we can write for instance
\begin{align*}
j^k=k![x^k]\sum_{n=0}^\infty\frac{(jx)^{n}}{n!}=k![x^k]e^{jx}\tag{1}
\end{align*}

We obtain for $k<n$:
\begin{align*}
\color{blue}{\sum_{j=0}^n(-1)^n\binom{n}{j}j^k}&=\sum_{j=0}^n(-1)^n\binom{n}{j}k![x^k]e^{jx}\tag{2}\\
&=k![x^k]\sum_{j=0}^n(-1)^j\binom{n}{j}e^{jx}\\
&=k![x^k]\left(1-e^x\right)^n\tag{3}\\
&=(-1)^nk![x^k]\left(x+\frac{x^2}{2}+\cdots\right)^n\tag{4}\\
&\,\,\color{blue}{=0}
\end{align*}
and the claim follows.

Comment:

*

*In (2) we apply the coefficient of operator according to (1).


*In (3) we use the binomial theorem.


*In (4) we factor out $(-1)^n$ and observe we have an expression in $x$ with smallest power of $x$ greater or equal to $n$.
A: There are three key steps to the proof, the first of which you've already found:

*

*Reduce the problem to proving the identity for $P=X^k$ for all nonnegative integers $k$ and $n$ with $k<n$.

*Reduce the problem to proving the identity for $P=1$ for all nonnegative integers $n$, by expressing the sum for $(k,n)$ in terms of sums with smaller parameters. Hint:

 Show that if $k\geq1$, the sum for $(k,n)$ is a linear combination of the sums for $(l,n-1)$ with $l<k$. This can be done very explicitly by manipulating binomial coefficients. Then by induction, the sum for $(k,n)$ is a multiple of the sum for $(0,n-k)$.



*Show that the identity holds for $P=1$ for all nonnegative integers $n$. Hint:

 Use the binomial theorem.

I might post a full solution at a later time, if it is needed.
Alternative hint:

 Show that for $f_n(P):=\sum_{i=0}^n(-1)^j\binom{n}{j}P(j)$ you have
 $$f_n(X^k)=-nf_{n-1}\left((X+1)^{k-1}\right).$$

A: For a combinatorial proof of the sum with $j^k$, note that both sides count the number of surjections from an $k$-set onto an $n$-set, which is $0$ when $k<n$. The summation is the inclusion-exclusion formula, where the $n$ properties to be avoided are that element $i$ is not in the image of the function.
A: Here is an approach. We first need a preliminary result.
Given a polynomial $P$ defiine $(\Delta P)(x)=P(x+1)-P(x)$ (the first difference operator). Given a polynomial $P$ where $P(x)= a_0 + a_1x + \cdots + a_nx^n$, we claim that
$$
\Delta^{n}(P)(x)=n!a_{n}\tag{0}\label0.
$$
To see this write
$$
 P(x) = \sum_{k=0}^{n} a_k x^k=  \sum_{k=0}^{n} a_k \sum_{m=0}^{k}S(k,m)x^{\underline{m}}\tag{1}\label1
$$
where $S(k,m)$ is the stirling number of the second kind. and $x^{\underline{m}}$ is the falling factorial. Since $\Delta(x^{\underline m})=mx^{\underline{m-1}}$, $\Delta^{n}(x^{\underline {m}})=m^{\underline n}x^{\underline{m-n}}$. If $m<n$, then $\Delta^{n}(x^{\underline {m}})=0$. Hence taking $\Delta ^{n}$ of both sides of (1) yields that
$$
(\Delta^nP)(x)=n!S(n,n)a_{n}=n!a_{n}\tag{2}\label2.
$$
Returning to the problem define $S(P)(x)=P(x+1)$ (shift operator), so $\Delta=S-I$ where $I(P)=P$ is the identity operator. Since $S$ and $I$ commute the binomial theorem implies that
$$
\Delta^n=(S-I)^n=\sum_{j=0}^n\binom{n}{j}(-1)^{n-j}S^j=(-1)^n\sum_{j=0}^n \binom{n}{j}(-1)^jS^j
$$
whence
$$
(\Delta^nP)(0)=(-1)^n\sum_{j=0}^n\binom{n}{j}(-1)^jP(j)\tag{3}.
$$
If $P$ is a polynomial of degree less than $n$, than $(\Delta^n)P=0$ by $(0)$, whence $(3)$ implies the result.
