Recursive equation of following code snippet

Question

Question

consider the following code snippet

A(n)
{
  if (n<1) return 1;
  else return A(n-2)+B(n-1)
}

B(n)
{
  if(n<=1) 
  return 1;
  else return B(n-1)+A(n-2)
}

find $A(6)$

My Approach & query

Its easy to calculate $A(6)$,it is coming as $16$.But i want to solve it using finding its recursive equation so that i can find $A(n)$ for any value of $n$.

I started as-:

$$A(n)=A(n-2)+B(n-1)$$ $$=A(n-2)+B(n-2)+A(n-3)$$ $$ =A(n-2)+A(n-3) +B(n-2)$$ But seriously i am hopeless to go further .please help me out to solve such type of question.

thanks

Answer 1

If you want to use the recursive definition, you have to start from the beginning, that is $A(-1) = A(0) = 1$, $B(0) = 1$ and $B(1) = 1$. Moreover, for $n \geqslant 2$, you get $$ A(n) = A(n-2) + B(n-1) = B(n-1) + A(n-2) = B(n) $$ Therefore, for $n \geqslant 3$, one gets $B(n-1) = A(n-1)$, whence $$ A(n) = A(n-2) + A(n-1) $$ Thus $A(n)$ is a Fibonacci type sequence: $$ A(0) = 1 \quad A(1) = 2 \quad A(3)= 4 \quad A(4) = 6 \quad A(5) = 10 \quad A(6) = 16 \quad \dotsm $$