سلام
دوست گرامی روش حل کلاسیک روابط بازگشتی از مباحث مهم به شمار می اید که گاها در تست ها مطرح می شود از جمله در سوالات ۱/۸ و ۱/۱۶ که شما مطرح کردید.اینکه بخواهید از روش دیگری مثلا درختی به جواب برسید گاهی سوال طوری است که بر مبنای خود مفاهیم روش کلاسیک است و استفاده از روش دیگر گاها غیرممکن ویا زمان بر است.بیشتر از روش های درختی و قضیه اصلی و قضیه اکرا و ... برای یافتن مرتبه استفاده می شود و لی گاها در سوال حل رابطه بازگشتی را می خواهد مثل ۱/۱۶ که صریحا عنوان پاسخ رابطه بازگشتی همگن را می خواهد.
در این دو سوال که شما عنوان کردید حتی اگر روش حل اصلی روابط بازگشتی را بلد نباشیم هم می توانیم جواب دهیم
در ۱/۱۶ گزینه ۱ مرتبه را مشخص میکند نه حل رابطه پس رد می شود. مقادیر توقف رابطه که در سوال ذکر شده در رابطه نهایی که در گزینه ها امده هم باید صدق کند[tex]T(0)=0\: \: \: \: \: \: T(1)=1\: \: \: \: \: T(2)=2[/tex]
برای گزینه ۳ [tex]T(0)=2^0-0\ast2^{-1}+C=0\: \: \rightarrow\: \: C=-1\: \: \: \: \: \: \: \: \: \: T(1)=2-1+C=1\: \: \: \rightarrow\: C=0[/tex]
که رد می شود چون دو مقدار متفاوت برای c بدست امد
برای گزینه ۴ هم [tex]T(0)=1+C=0\: \: \rightarrow\: \: C=-1\: \: \: \: \: \: T(1)=2-\frac{1}{2}+C=1\: \: \: \rightarrow\: \: C=-\frac{1}{2}[/tex]
که رد می شود پس گزینه دو درست است اگر رابطه را حل کنیم همیمن گزینه ۲ بدست می اید با C= -2
در ۱/۸ هم نیازی به حل کامل نیست
[tex]G_i=G_{i-1}+2G_{i-2}+G_{i-3}\le4G_{i-1}=4^iG_0[/tex]
که [tex]G_0=1[/tex] پس گزینه ۱ صحیح است شاید این سوال پیش اید که گزینه ۴ هم می تواند جواب باشد ولی در عنوان سوال گفته کدام یک جواب بهتری است.