Riordan numbers recurrence Let be $C_n$ the $n^{th}$ Catalan's number.
Well, I have the following relation:
$$f(n)=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}C_k\text{.}$$
I would like to know, if there is a way to obtain the recurrence:
$$f(n)=\frac{n-1}{n+1}(2f(n-1)+3f(n-2))$$
just by the first identity.
Thanks in advantage!
Good evening!
PS: The problem I'm trying to solve il the following: Let be $f(n)$ number of non-crossing partitions of $[n]={1,2,...,n}$ without singeltons, find a recurrence for $f(n)$.
By using the inclusion–exclusion principle, I've obtained the first relation. Now, I would like to find a recurrence.
 A: 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.
