2

Is there an easy way to solve a recurrence given with two variables and three different functions? Actually I'm looking for the solution of:

$$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1) $$ $$R(n,k)=A(n-1,k-1)+ R(n-1,k-1)$$ $$L(n,k)=A(n-1,k-1)+ L(n-1,k-1)$$

For the initial value I have: $A(1,0)=1$, $L(0,0)=1$, $R(0,0)=0$ and: $$ A(n,k)=0 \text{ if }k+1>n \text{ or } n>3*k+1$$ $$ R(n,k)=0 \text{ if }k+1>n \text{ or } n>3*(k-1)+2$$ $$ L(n,k)=0 \text{ if }k>n \text{ or } n>3*(k-1)+2$$

I have no clues of where to start ... Any idea or even (free) tools would be welcome.

Thanks.

I edited because may inequality where mixed up. Sorry. It should be correct now I also addes some initial value for R and L. Not sure it's necessary but it cannot hurt...

wece
  • 2,732

1 Answers1

0

I assume that $n,k\ge 0$. When I analyze such recurrences, usually I fill tables with their values (in your case the tables for $A$, $L$, and $R$ should be filled simultaneously) and I often wrote computer programs for this purpose. Then I look at the data, try to guess its asymptotic behavior, and, with a luck, its closed forms. See, for instance, a thread started by my question. I tried to fill table for $A$, but I failed to find $A(2,1)$.

Also I looked for a self-sufficient recurrent formula for $A$, which then can be implemented by Excel. I proceeded as follows.

Provided $n\ge 4$ and $k\ge 2$ we have

$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1)$

$A(n-1,k-1)=A(n-3,k-2)+A(n-4,k-2)+R(n-3,k-2)+L(n-3,k-2)$.

Thus $$A(n,k)- A(n-1,k-1)=$$ $$A(n-2,k-1)- A(n-3,k-2)+A(n-3,k-1)- A(n-4,k-2)+R(n-2,k-1)- R(n-3,k-2)+L(n-2,k-1) - L(n-3,k-2)=$$ $$A(n-2,k-1)- A(n-3,k-2)+A(n-3,k-1)- A(n-4,k-2)+A(n-3,k-2)+A(n-3,k-2)=$$ $$A(n-2,k-1)+A(n-3,k-1)+A(n-3,k-2)-A(n-4,k-2).$$

Hence

$$A(n,k)=A(n-1,k-1)+ A(n-2,k-1)+A(n-3,k-1)+A(n-3,k-2)-A(n-4,k-2).$$

Alex Ravsky
  • 90,434