**How to approach the following two dimensional recurrence relation ?**

For ,

where (for ) and (for .

**Solution**:

One way to go about this and generally about solving recurrence relations is to use generating functions, in this case this will lead to two variable generating function.

Let’s suppose we have formal powers series which encodes coefficients of your sequence. For simplicity, here we have it shifted, so actually , but don’t worry about that, we can shift this back at the end. Now let’s play with coefficients a little to see if we can get better form of :

Now we have shifted the indices (you will see later why), but before proceeding, notice and that

and similarly for the second sum. So overall we have

Now for the rightmost sum, lets write

Here we have just applied the recurrence relation (this is why we moved the indices out before) and then moved the , out of the sum, so that indices match. Now lets just re-index the sum

Here we have just substituted back the definition of itself. Now putting back together we have

and after some simple algebraic manipulations we finally get:

Now the encodes all of the coefficients in a compact way. We can now try to write it in a way that will allow us to see the coefficients more clearly.

For this notice that . Also second expression is well known generating function

So we can view our function in this form as a product

Now to ask what is the value of is same as to ask what coefficient of is in this product. It is not hard to see that it will be . So overall, also with correcting the original offset from to and to , we get