<s>[INST] 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. 
 [/INST] 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}}$).
</s>