How to find the closed form solution for the multivariate recurrence?

Question

Recurrence relation:

f(n,k) = f(n-1,k) + f(n-1,k-1) + f(n-2,k-1)  

Initial conditions:

f(n,0) = 1, f(n,1) = 2n, f(n,n) = 2  
f(n,k) = 0 for n < k

Answer 1

Consider the polynomials $p_n(x) = \sum_{k=0}^n f(n,k) x^k$. Then the recurrence becomes $p_{n}(x) = (x+1) p_{n-1}(x) + x p_{n-2}(x)$ with $p_0(x)=1$ and $p_1(x) = 1+2x$. The generating function is $$ g(t,x) = \frac{1+tx}{1-(1+x)t - xt^2}$$ Hmm... seems to be OEIS sequence A035607.