تعداد کلمات $n$ حرفی با $a,b,c$ با فرد حرف $a$ را بیابید(با استفاده از رابطه بازگشتی).
روش من: اگر $f_n$ را جواب سوال و $g_n$ را همان کلمات با زوج حرف $a$ بنامیم داریم:
$f_n=2f_{n-1}+g_{n-1}$
$g_n=2g_{n-1}+f_{n-1}$
با تفاضل کم کردن این دو رابطه داریم:
$g_n-f_n=g_{n-1}-f{n-1}=\dots =g_1-f_1=1$
پس داریم:
$f_n=3f_{n-1}+1$
اما کتاب جواب $f_n=4f_{n-1}-3f_{n-2}$ را داده که هم ارز هستند اما چگونه به روش ترکیبیاتی می توان این رابطه را به دست اورد؟
