سوال ۴

اگر مسیر قورباغه را انتخاب کنیم، اعداد خانه‌های مسیر(به جز خانه‌ی آخر) به طور یکتا مشخص می‌شوند.

روی تعداد خانه‌های مسیر حالت‌بندی کنید.

این راه‌حل به صورت بازگشتی عمل می‌کند!
اگر جدول $2$ خانه داشت، ایلیچ به چند روش می‌توانست اعداد یک تا پنج را در خانه‌های آن بنویسد، طوری که قورباغه پس از تعدادی گام به خانه‌ی سمت راست جدول برسد؟
اگر جدول $3$ خانه داشت چطور؟

پاسخ حالتی که جدول $2$ خانه داشته باشد:
در خانه‌ی اول جدول(خانه سمت چپ) باید عدد $1$ نوشته شده باشد؛ چون در غیر اینصورت قورباغه نمی‌پرد. عدد خانه‌ی آخر(خانه‌ی سمت راست) تاثیری در مسیر قورباغه ندارد و می‌تواند هر کدام از اعداد $1$ تا $5$ باشد.
پس در حالتی که جدول $2$ خانه داشته باشد، ایلیچ به $5$ روش می‌تواند اعداد را در خانه‌های آن بنویسد.

پاسخ حالتی که جدول $3$ خانه داشته باشد:
در خانه‌ی اول جدول باید یکی از اعداد $1$ یا $2$ نوشته شده باشد.
اگر عدد خانه‌ی اول، $1$ باشد، قورباغه پس از یک پرش به خانه‌ی دوم می‌رسد؛ پس(طبق راهنمایی قبلی) در این حالت خانه‌های دوم و سوم را به $5$ روش می‌توانیم پر کنیم، طوری که قورباغه به خانه‌ی آخر(خانه‌ی سوم) برسد.
اگر عدد خانه‌ی اول، $2$ باشد، قورباغه با اولین پرش به خانه‌ی آخر می‌رسد؛ پس هرکدام از خانه‌های دوم و سوم را به $5$ روش می‌توانیم پر کنیم.
در نتیجه، پاسخ برای حالتی که جدول $3$ خانه داشته باشد برابر است با:
$$ 5 + 5 * 5 = 30 $$

اگر پاسخ را، در حالتی که جدول n خانه دارد، f(n) بنامیم، سعی کنید رابطه‌ای بازگشتی برای f(n) بیابید. (می‌توانید با تلاش برای محاسبه‌ی f(۴) شروع کنید!)

نشان دهید $f(n) = 6 * f(n - 1)$؛ به ازای $n > 2$.