سلام. شرط همگرایی تو بازگشتی اینه که مخرج رابطه بازگشتی بزرگتر از یک باشه. به نظرم هیچ گزینه ای چنین تضمینی نداره. فقط در شرایطی که تمام مقادیر در گزینه ۴ بزرگتر از ۱ باشن درسته.

این تست غلطه چون گزینه صحیح نداره اما بهترین گزینه موجود گزینه ۴ است.

چون گفته مقادیر ai ها صحیح و مثبته پس وقتی k تا عدد صحیح و مثبت با هم جمع بشن مسلما حاصلش از k و ۱ بیشتره(چونk هر عددی می تونه باشه مثلا جمع سه تا عدد صحیح و مثبت حتما بزگتر مساوی ۳ است پس گزینه ۱ نادرسته)
پس گزینه های ۱ و ۳ غلطند

بررسی گزینه دو:
جمع k تا عدد صحیح و مثبتت تنها در صوریتی k می شود که تک تک اعداد ۱ باشند
که در این صورت اصلا رابطه بازگشتی نخواهد بود و حل ندارد.
چون مثلا اگر k=2 باشد رابطه ی [tex]T(n)=T(n) T(n) \theta(n)[/tex] بی معناست چون اگر مثلا T(1)=1 فرض کنیم و دوباره همین رابطه را روی آن اعمال کنیم مقدار T(1) مدام تغییر می کند
گزینه های ۱ و ۲ و ۳ به وضوح غلطندو گزینه ی ۴ گزینه ی همواره درستی نیست یعنی شرط ذکر شده در گزینه چهار کافی نیست .

توضیح گزینه چهار:
طبق قضیه مستر می دانیم که در رباطه ی [tex]T(n)=aT(\frac{n}{b}) \theta(n)[/tex] صورتی پیچیدگی این رابطه [tex]\theta(n)[/tex] خواهد بود که رشد [tex]n^{\log_b^a}[/tex] از n کمتر باشد واین در صورتی رخ می دهد که a<b باشد یعنی کسر a/b کوچکتر از ۱ باشد
پس مسلمه که در [tex]T(n)=SigmaT(\frac{n}{a_i}) \theta(n)[/tex] باید مجموع اعداد مخرج از k بیشتر باشد. اما این شرط کافی نیست یعنی صرف برقرار بودن این شرط نمی اند [tex]\theta(n)[/tex] بودن رابطه را تضمین کند
مثلا در حالتی که K=2 و [tex]a_1=a_2=3[/tex] باشد رابطه [tex]\theta(n)[/tex] است
اما در حالتی که K=2 و [tex]a_1=a_2=2[/tex] باشد رابطه [tex]\theta(n)[/tex] نیست.