# Inclusion-exclusion related identities

$1.$ Prove $\forall n\in\mathbb{N}\quad n\geq5$$n^4-\binom{n}{1}(n-1)^4+\binom{n}{2}(n-2)^4-\binom{n}{3}(n-3)^4+\dots +(-1)^{n-2}\binom{n}{n-2}\cdot2^4+(-1)^{n-1}\binom{n}{n-1}\cdot1^4=0$$$2.$Prove$\forall n\in\mathbb{N}\quad$$n!=\sum\limits_{k=0}^{n} (-1)^k\binom{n}{k}(n-k)^n$$

Progress:
$1.$ My intuition here is that $n^4$ represent the number of all functions, say $f:A\to B$ where $|A|=4$ and $|B|=n$, though I'm not quite sure what the other elements represent according to the inclusion-exclusion principle.

$2.$ My intuition here is that the number of injective functions, say $f:A\to A$ where $|A|=n$ is equal to the number of surjective functions. The first element of the sum, $n^n$ is the total amount of functions $f:A\to A$ and apparently we define $A_{i}=\{f:A\to A|\quad\forall a\in A\quad f(a)\neq i\}$ and use the inclusion-exclusion principle.

Corrections/suggestions would be much appreciated

• calculus of finite differences? – Lord Shark the Unknown Dec 17 '17 at 13:20
• Think about counting surjections $\{1,2,3,4\}\to\{1,2,\ldots,n\}$. – Lord Shark the Unknown Dec 17 '17 at 13:23
• Is that even possible? if $n>4$ there would be no surjections – Slavik Egorov Dec 18 '17 at 8:46
• And you get the answer zero. – Lord Shark the Unknown Dec 18 '17 at 8:47