アルゴリズムの問題でお聞きしたいです。
↓の16ページ目　第6問です（ｐｄｆ）
ttp://www.i.u-tokyo.ac.jp/edu/course/ipc/pdf/2004system-j.pdf


（1）は
C(A,1) = 1;
C(B,1) = 0;

C(A,n) = C(A,n-1) + C(B,n-1);
C(B,n) = C(B,n-2) + C(A,n-2);

(2) は
空欄１　;　r = 1;
空欄２　; r = 0;
空欄３　;
if( p == 'A'){ r = path('A',n-1) + path('B' , n-1);}
if( p == 'B'){ r = path('A',n-2) + path('B' , n-2);}

と自分で答えを出しましたが　（３）がわかりません。
漸化式を解いてそれを表現するだけだと思ったのですが　うまくいきません。
よろしくお願いいたします。