Solve recurrence relation!

Question

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.

Answer 1

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}}$).

Answer 2

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.