How to solve this recurrence $$S(m,n)=S(m,n-1)+S(m-1,n-1)+S(m-1,n)$$ with base conditions $$S(1,1)=3,\; S(0,n)=S(m,0)=1.$$
This recurrence came up when I tried to solve this problem: Find the number of paths from lower most left corner to uppermost right corner if one can move horizontally, vertically and diagonally. I have a combinatorial solution but want it through this recurrence.