Solve recurrence relation! I was working with this recurrence relation :

$$\begin{cases}A(n,k) = A(n-1, k-1)+A(n-2, k-1)+A(n-1, k)\\
A(n, 0) = 1\\
A(n, 1) = 2n
\end{cases}$$
  Generating function : $(1+x)/(1-x-x*y-x^2*y)$

Now since this involves two parameters, I tried changing it to a single parameter by fixing $k$ and iterating over $n$ for $n=k$, $n=k+1$, $n=k+2$.. and so on.
What I found was that $A(k, k)=2$, $A(k+1, k)=4k$, $A(k+2, k)=4k^2+2$ and the later results were too haphazard to write i.e. they did not form a pattern to the previous formulas. I tried to use the above equation to find characteristic roots and use $A(n) = a(x^n)+b(y^n)$ where $x$ and $y$ are roots. However, I wasn't able to compute it correctly.
What am I missing here? Am I tackling the problem in a complete wrong way? Is there any other method to solve such recurrences? Any help is appreciated. I assume the formula for $A(n)$ could be pretty cumbersome but I still wish to find it. 
 A: We look at the generating function $\frac{1+x}{1-x-xy-x^2y}$ and derive the coefficients $A(n,k)$. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain
  \begin{align*}
\color{blue}{A(n,k)}&=[x^ny^k]\frac{1+x}{1-x-xy-x^2y}\\
&=[x^ny^k]\frac{1+x}{1-x-x(1+x)y}\\
&=[x^ny^k]\frac{1+x}{1-x}\cdot\frac{1}{1-\frac{x(1+x)}{1-x}y}\\
&=[x^n]\frac{1+x}{1-x}[y^k]\sum_{j=0}^\infty\left(\frac{x(1+x)}{1-x}\right)^jy^j\tag{1}\\
&=[x^n]\frac{1+x}{1-x}\left(\frac{x(1+x)}{1-x}\right)^k\tag{2}\\
&=[x^{n-k}]\frac{(1+x)^{k+1}}{(1-x)^{k+1}}\tag{3}\\
&=[x^{n-k}](1+x)^{k+1}\sum_{j=0}^\infty\binom{-k-1}{j}(-x)^j\tag{4}\\
&=[x^{n-k}](1+x)^{k+1}\sum_{j=0}^\infty\binom{k+j}{j}x^j\tag{5}\\
&=\sum_{j=0}^{n-k}\binom{k+j}{j}[x^{n-k-j}](1+x)^{k+1}\tag{6}\\
&=\sum_{j=0}^{n-k}\binom{k+j}{j}\binom{k+1}{n-k-j}\tag{7}\\
&\,\,\color{blue}{=\sum_{j=0}^{n-k}\binom{n-j}{k}\binom{k+1}{j}}\tag{8}
\end{align*}

Comment:


*

*In (1) we do a geometric series expansion with respect to $y$.

*In (2) we select the coefficient of $y^k$.

*In (3) we do some simplifications and apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.

*In (4) we do a binomial series expansion.

*In (5) we apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

*In (6) we select the coefficient of $x^{n-k}$ and restrict the upper bound of the sum by $n-k$ since other terms do not contribute to $[x^{n-k}]$.

*In (7) we select the coefficient of $x^{n-k-j}$.

*In (8) we do a final rearrangement by changing the order of summation $j\to n-k-j$.

We use the formula (8) to check the boundary conditions. We obtain
  \begin{align*}
A(n,0)&=\sum_{j=0}^n\binom{n-j}{0}\binom{1}{j}=\sum_{j=0}^n\binom{1}{j}=\begin{cases}
1&\qquad\qquad\qquad\qquad n=0\\
2&\qquad\qquad\qquad\qquad n>0
\end{cases}\\
A(n,1)&=\sum_{j=0}^{n-1}\binom{n-j}{1}\binom{2}{j}=\sum_{j=0}^{n-1}(n-j)\binom{2}{j}=\begin{cases}
1&\qquad n=1\\
4(n-1)&\qquad n>1
\end{cases}
\end{align*}
  We observe, the generating function $\frac{1+x}{1-x-xy-x^2y}$ does not follow OPs stated boundary conditions $A(n,0)=1\ (n\geq 0)$ and $A(n,1)=2n\ (n\geq 1)$ and this is a reason for the difficulties OP has to cope with.

Note: We find with some help of Wolfram Alpha a series expansion
\begin{align*}
\frac{1+x}{1-x-xy-x^2y}&=1+(2+y)x+(2+4y+y^2)x^2+(2+8y+6y^2+y^3)x^3\\
&\qquad+(2+12y+18y^2+8y^3+y^4)x^4+\cdots
\end{align*}
The corresponding sequence of the coefficients $A(n,k)$ starting with 
\begin{align*}
&1;\\
&\color{blue}{2},\color{blue}{1};\\
&\color{blue}{2},\color{blue}{4},1;\\
&\color{blue}{2},\color{blue}{8},6,1;\\
&\color{blue}{2},\color{blue}{12},18,8,1;\ldots
\end{align*}
can be found as A113413 in OEIS. We can find there OPs stated generating function $\frac{1+x}{1-x-xy-x^2y}$ as well as the recurrence relation $A(n,k) = A(n-1, k-1)+A(n-2, k-1)+A(n-1, k)$, but we have different boundary conditions (marked above in $\color{blue}{\mathrm{blue}}$).
A: 
Here we solve OP's recurrence relation by a generating function approach. We will see the recurrence relation leads to a slightly different generating function than stated by OP due the specific boundary conditions. Then we use the generating function to show 
  \begin{align*}
\color{blue}{A(n,k)=\sum_{j=0}^{n-k}\binom{k+j}{j}\binom{k}{n-k-j}+\sum_{j=0}^{n-k}\binom{k+j-1}{j}\binom{k-1}{n-k-j}[[k\geq 1]]}\tag{1}
\end{align*}

We use in (1) Iverson brackets $[[k\geq 1]]$ which is $1$ iff $k\geq 1$ and $0$ otherwise. 
Note: OP's recurrence relation is not completely specified. We add a boundary condition $A(0,k), k\geq 1$ which do not conflict with anything else and consider
\begin{align*}
A(n,k) &= A(n-1, k-1)+A(n-2, k-1)+A(n-1, k)\tag{2}\\
A(n, 0) &= 1\\
A(n, 1) &= 2n\\
\color{blue}{A(0, k) }&\color{blue}{= 0\qquad k\geq 1}
\end{align*}

We define the generating function $a(x,y)=\sum_{n,k\geq 0}A(n,k)x^ny^k$ and obtain from the recurrence relation (2)
  \begin{align*}
\sum_{{n\geq 2}\atop{k\geq 1}}&A(n,k)x^ny^k\\
&=\sum_{{n\geq 2}\atop{k\geq 1}}A(n-1,k-1)x^ny^k+\sum_{{n\geq 2}\atop{k\geq 1}}A(n-2,k-1)x^ny^k
+\sum_{{n\geq 2}\atop{k\geq 1}}A(n-1,k)x^ny^k\\
&=xy\sum_{{n\geq 1}\atop{k\geq 0}}A(n,k)x^ny^k+x^2y\sum_{{n\geq 0}\atop{k\geq 0}}A(n,k)x^ny^k
+x\sum_{{n\geq 1}\atop{k\geq 1}}A(n,k)x^ny^k\\
&=xy\left(a(x,y)-\sum_{k\geq 0}A(0,k)y^k\right)+x^2ya(x,y)+x\left(a(x,y)-\sum_{n\geq 0}A(n,0)x^n-\sum_{k\geq 0}A(0,k)y^k+1\right)\\
&=xy\left(a(x,y)-1\right)+x^2ya(x,y)+x\left(a(x,y)-\sum_{n\geq 0}x^n-1+1\right)\\
&=xy\left(a(x,y)-1\right)+x^2ya(x,y)+x\left(a(x,y)-\frac{1}{1-x}\right)\tag{3}
\end{align*}

Since
\begin{align*}
\sum_{{n\geq 2}\atop{k\geq 1}}A(n,k)x^ny^k&=a(x,y)-\sum_{n\geq 0}A(n,0)x^n-\sum_{k\geq 1}A(k,0)y^k-x\sum_{k\geq 1}A(k,1)y^k\\
&=a(x,y)-\frac{1}{1-x}-2xy\tag{4}
\end{align*}

Putting (3) and (4) together we obtain
  \begin{align*}
\color{blue}{a(x,y)}&\color{blue}{=\frac{1+xy}{1-x-xy-x^2y}}\\
&=\color{blue}{1}+(\color{blue}{1}+\color{blue}{2}y)x+(\color{blue}{1}+\color{blue}{4}y+2 y^2)x^2+(\color{blue}{1}+\color{blue}{6}y+8y^2+2 y^3)x^3\\
&\qquad + (\color{blue}{1}+\color{blue}{8}y+18y^2+12y^3+2y^4)x^4+\cdots
\end{align*}
  where the expansion was done with some help of Wolfram Alpha. The coefficients specified by the boundary conditions are marked in blue.

Note, the numerator $1+xy$ in $a(x,y)$ which is different to the numerator $1+x$ stated in OP's generating function.

Now we derive the formula (1) for $A(n,k)$. Since the derivation is similar to that of my other answer the comments and a few details are omitted. We obtain
  \begin{align*}
\color{blue}{A(n,k)}&\color{blue}{=[x^ny^k]\frac{1+xy}{1-x-xy-x^2y}}\\
&=[x^ny^k]\frac{1+xy}{1-x-x(1+x)y}\\
&=[x^ny^k]\frac{1+xy}{1-x}\sum_{j=0}^\infty\left(\frac{x(1+x)}{1-x}\right)^jy^j\\
&=[x^{n-k}]\frac{(1+x)^k}{(1-x)^{k+1}}+[x^{n-k}]\frac{(1+x)^{k-1}}{(1-x)^k}[[k\geq 1]]\\
&=[x^{n-k}](1+x)^k\sum_{j=0}^\infty\binom{k+j}{j}x^j+[x^{n-k}](1+x)^{k-1}\sum_{j=0}^\infty\binom{k+j-1}{j}x^j[[k\geq 1]]\\
&\,\,\color{blue}{=\sum_{j=0}^{n-k}\binom{k+j}{j}\binom{k}{n-k-j}+\sum_{j=0}^{n-k}\binom{k+j-1}{j}\binom{k-1}{n-k-j}[[k\geq 1]]}
\end{align*}
  and the claim (1) follows.

