سوال ۹

گزینه (۲) درست است.

$a_n$ را تعداد حالات خواسته شده برای یک گراف $2n$-راسی در نظر می‌گیریم. $b_n$ را نیز مانند $a_n$‌ تعریف می‌کنیم؛ با این تفاوت که از قبل بدانیم بین دو راس سمت چپ مسیری وجود داشته است. داریم:

$$a_n=3a_{n-1}+b_{n-1}$$

و

$$b_n=4a_{n-1}+2b_{n-1}$$

از روابط بازگشتی بالا مقدار $a_{10}$ که پاسخ مسئله است به‌دست می‌آید.