# Issue solving recurrence relation

I´m trying to solve the following recurrence relation:

RSolve[{a[n + 1, k + 1] == a[n, k + 1] + a[n, k] + Binomial[n - 1, k],
a[n, k] == 0 && (k <= 0 || n < k), a[n, 1] == n && 1 <= n},
a[n, k], {n, k}]

However, when I execute the above function, it returns an error:

RSolve::deqn: Equation or list of equations expected instead of k<=0||n<k in the first argument {a[1+n,1+k]==a[n,k]+a[n,1+k]+Binomial[-1+n,k],a[n,k]==0&&(k<=0||n<k),a[n,1]==n&&1<=n}.

I think the problem is the representation of boundary conditions, here you have a full definition of the recurrence:

$$a_{n+1,k+1} = a_{n,k+1}+a_{n,k}+\binom{n-1}{k}\qquad\text{if }\;0\le k\;\text{ and }\;1\le n$$

$$a_{n,k}=\begin{cases} 0&\quad\text{if }\;k\le 0\;\text{ or }\;n\lt k\\ n&\quad\text{if }\;k=1\le n\end{cases}$$

• You cannot specify boundary conditions like this. You could write a[n,0]=0 and a[n,1]=n, but I don't think you can specify that a[n,k]=0 for n<k. Anyway, I don't think Mathematica will be able to solve your recurrence relation -- it's unable to do anything if you keep only the "simple" boundary conditions. I think it only knows how to handle very few recurrence relations with multiple variables. Commented Jul 11 at 9:59
• As @NajibIdrissi commented, your problem has a boundary condition along the diagonal n==k. If I were you, I will rewrite the recursion in terms of b[n,k] = a[n,n-k]. Then, the boundary is now along k=0, and Mathematica will easily solve the problem. Commented Jul 12 at 6:38