Riordan numbers recurrence

Solution 1:

This is typically a problem where Zeilberger's algorithm applies (in fact, you don't need the full algorithm, just the "creative telescoping" method part). It may not the prettiest method but it is systematic and gets the job done in your case.

Denote the summand by

$$ F(n,k)=(-1)^{n-k}\binom{n}{k}C_k \tag{1} $$

As is standard, we define $\binom{n}{k}$ to be $0$ when $k \gt n$ or $k\lt 0$, so that $F(n,k)=0$ also for those values.

We start with the remark that

$$ \frac{F(n+1,k)}{F(n,k)}=\frac{-(n+1)}{n-k}, \frac{F(n,k+1)}{F(n,k)}=\frac{-(n-k)(4k+2)}{(k+1)(k+2)} \tag{2} $$

The first step of the algorithm is to deduce from iterations of (2), a linear relation between translates $F(n+i,k+j)$ of $F$. After getting inspiration from the form of the final result you're seeking and a little bit of trial and error, I found the following (there are some software that compute this directly, but unfortunately all the ones I know of, such as Maple, are behind a paywall) :

$$ \begin{array}{ll} \quad & -4(n+1)F(n,k) +(n+1)F(n,k+1)-(4n+6)F(n+1,k)\\ & +(2n+4)F(n+1,k+1)+(n+3)F(n+2,k+1)=0 \end{array} \tag{3} $$

This identity can be rewritten as

$$ \begin{array}{l} \quad & 3(n+1)F(n,k) +2(n+1)F(n+1,k)-(n+3)F(n+2,k) \\ & =G(n,k+1)-G(n,k) \end{array} \tag{3'} $$

where $G(n,k)=(n+1)F(n,k)+(2n+4)F(n+1,k)+(n+3)F(n+2,k)$. Summing (3') for $k$ between $0$ and $n+2$ inclusive, we obtain (remembering our conventions for value of $F$ on overflowing arguments) :

$$ \begin{array}{l} \quad & 3(n+1)f(n)+2(n+1)f(n+1)-(n+3)f(n+2) \\ = & G(n,n+3)-G(n,0)=0 \end{array}\tag{4} $$

because $G(n,0)=(-1)^n(n+1-(2n+4)+n+3)=0$ and $G(n,n+3)=(n+1)\times 0+(2n+4)\times 0 +(n+3)\times 0 = 0$. This finishes the proof of your identity.