You are not allowed to perform this action

سوال ۱۱

برای مقادیر صحیح $x \ge 0$ و $y \ge 0$، تابع $A(x, y)$ را به این صورت تعریف می‌کنیم:

\[ \begin{eqnarray*} A(0, y) & = & y + 1
A(x + 1, 0) & = & A(x, 1)
A(x + 1, y + 1) & = & A(x, A(x + 1, y)) \end{eqnarray*} \]

مقدار $A(1, y)$ برای کلیه‌ی مقادیر نامنفی $y$ چه‌قدر است؟

پاسخ

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

$$A(1,y)=A(0+1,(y-1)+1)=A(0,A(1,y-1))=A(1,y-1)+1$$

در تساوی‌های فوق ابتدا از فرض سوم و سپس از فرض اول استفاده شده است. به استقرا ثابت می‌شود که:

$$A(1,y)=A(1,0)+y$$

و اما با توجه به فرض دوم مسئله٬ $A(1,0)$ به شکل زیر به‌دست می‌آید:

$$A(1,0)=A(0+1,0)=A(0,1)=1+1=2$$

پس:

$$A(1,y)=2+y$$

اُپدیا