USA IMO

First Solution. (By Tiankai Liu) Let $$f(k)=(n+1-k)!(n+k)!$$ for integers $0\le k\le n+1$. Note that $$\begin{array}{rl}f(k)+f(k+1)& =(n+1-k)!(n+k)!+(n-k)!(n+k+1)!\\ & =(n+1-k+n+k+1)(n-k)!(n+k)!\\ & =2(n+1)(n-k)!(n+k)!.\end{array}$$ Therefore, $$\begin{array}{rl}\sum _{k=0}^n(-1{)}^k(n-k)!(n+k)!& =\frac{1}{2(n+1)}\sum _{k=0}^n(-1{)}^k[f(k)+f(k+1)]\\ & =\frac{f(0)+(-1{)}^{n}f(n+1)}{2(n+1)}\\ & =\frac{(n+1)!n!+(-1{)}^{n}0!(2n+1)!}{2(n+1)}\\ & =\frac{(n!{)}^2}{2}+\frac{(-1{)}^n(2n+1)!}{2(n+1)}.\end{array}$$

Second Solution. (by Gabriel Carroll) Let $$f(x)=\sum _{k=0}^{\infty }k!x^k\text{and}g(x)=f(x)f(-x).$$ Note that $$\begin{array}{rl}{f}^{\prime }(x)& =\sum _{k=0}^{\infty }(k+1)!(k+1)x^k\\ & =\sum _{k=0}^{\infty }(k+2)!x^k-\sum _{k=0}^{\infty }(k+1)!x^k\\ & =\frac{f(x)-x-1}{x^2}-\frac{f(x)-1}{x}\\ & =\frac{f(x)(1-x)-1}{x^2}\end{array}$$ and $$\begin{array}{rl}{g}^{\prime }(x)& =f(-x)f^{\prime }(x)-f(x)f^{\prime }(-x)\\ & =\frac{f(-x)f(x)(1-x)-f(-x)}{x^2}-\frac{f(x)f(-x)(1+x)-f(x)}{x^2}\\ & =\frac{f(x)-f(-x)}{x^2}-\frac{2g(x)}{x}.\end{array}$$ Denote by $[x^k]h(x)$ the coefficient of $x^k$ in a power series $h(x)$. We have $$\begin{array}{rl}[x^{2n}]g(x)& =\frac{1}{2n}[x^{2n-1}]g^{\prime }(x)\\ & =\frac{1}{2n}[x^{2n-1}]\left(\frac{f(x)-f(-x)}{x^2}-\frac{2g(x)}{x}\right)\\ & =\frac{[x^{2n+1}](f(x)-f(-x))}{2n}-\frac{[x^{2n}]g(x)}{n}.\end{array}$$ It follows that $$[x^{2n}]g(x)\left(1+\frac{1}{n}\right)=\frac{2(2n+1)!}{2n},$$ or $$[x^{2n}]g(x)=\frac{(2n+1)!}{n+1}.(1)$$ --- On the other hand, $$\begin{array}{rl}g(x)& =f(x)f(-x)=\sum _{k=0}^{\infty }k!x^k\sum _{k=0}^{\infty }(-1{)}^{k}k!x^k\\ & =\sum _{n=0}^{\infty }\left(\sum _{k=0}^n(-1{)}^{n-k}k!(n-k)!\right)x^n.\end{array}$$ It follows that $$\begin{array}{rl}[x^{2n}]g(x)& =\sum _{k=0}^{2n}(-1{)}^{2n-k}k!(2n-k)!=\sum _{k=0}^{2n}(-1{)}^{k}k!(2n-k)!\\ & =2\sum _{k=0}^n(-1{)}^{k}k!(2n-k)!-(-1{)}^{n}n{!}^2\\ & =2\sum _{m=0}^n(-1{)}^{n-m}(n-m)!(n+m)!-(-1{)}^{n}n{!}^2.\end{array}$$ The last step can be seen easily by taking $m=n-k$. Thus, $$[x^{2n}]g(x)=2\sum _{k=0}^n(-1{)}^{n-k}(n-k)!(n+k)!-(-1{)}^{n}n{!}^2,$$ or $$(-1{)}^n[x^{2n}]g(x)+n{!}^2=2\sum _{k=0}^n(-1{)}^{-k}(n-k)!(n+k)!(2)$$ Combining (1) and (2) yields $$\begin{array}{rl}\sum _{k=0}^n(-1{)}^k(n-k)!(n+k)!& =\frac{(-1{)}^n[x^{2n}]g(x)+(n!{)}^2}{2}\\ & =\frac{(-1{)}^n(2n+1)!}{2(n+1)}+\frac{(n!{)}^2}{2}.\end{array}$$