سلام. ۴ که چیزی نداره. سمت چپ تساوی هست مجموع (f(m تا (f(n و سمت چپ هم هست مجموع (f(m-k+k تا (f(n-k+k که فقط یه عدد ثابت ازش کم شده و دوباره اضافه شده.. n-k+k=n و m-k+k=m.
۶ و ۷ رو با استقرا باید ثابت کرد. برای n=1 برقراره. فرض کنید برای n=k درسته و این نتیجه برسید که برای n=k+1 هم رابطه برقراره.

(۰۱ شهریور ۱۳۹۱ ۰۹:۵۱ ب.ظ)mehrdad66 نوشته شده توسط:  توی کتاب پوران پژوهش فصل اول صفحه ۴ فرمول های سیگما رو اینطور نوشته


گزینه ۴ رو بکل مشکل دارم
گزینه ۵ رو کامل میدونم

اگر امکان داره کسی برام فرمول ۶ و۷ رو در حد یه راهنمایی کوچیک هم باشه توضیح بده

اثبات ۵ و ۶ و ۷ با استقرا هست. بعنوان نمونه بنده ۷ رو با استقرا ثابت میکنم؛ امیدوارم یه آشنایی جزیی با استقرا داشته باشید (اثبات ۵ و ۶ راحت تر هست).
رابطه ۷ برای [tex]n=1[/tex] بوضوح برقراره (پایه استقرا). حالا فرض کنید این رابطه برای [tex]n=k[/tex] برقرار باشه(یعنی [tex]\sum_{i=1}^{k}i^3=\Big(\frac{k(k 1)}{2}\Big)^2[/tex]). ثابت می‌کنیم رابطه برای [tex]n=k 1[/tex] نیز برقراره:

دوستان واقعا ممنون اونم جواب دادن توی ۲۰ دقیقه بعد از ارسال سوال

رفتم درباره استقرا اطلاعاتی جمع کردم تا روش حل این سیگما رو یاد بگیرم گفتم شاید دوستانی بعد از من هم این مشکل براشون پیش بیاد ، اطلاعات جمع آوری شده رو ضمیمه کردم

آیا !logn محدود به چند جمله ای است؟
nlogn=logn!
من این دوتارو نفهمیدم

(۱۶ شهریور ۱۳۹۱ ۱۰:۴۹ ب.ظ)hadiseh67 نوشته شده توسط:  آیا !logn محدود به چند جمله ای است؟
nlogn=logn!
من این دوتارو نفهمیدم

اگر این تابع بخواد محدود به چند جمله‌ای باشه٬ باید:

[tex]\\ log(f(n))=O(logn) \\ log(n!) \approx \Theta(nlogn) \\ log(\Theta(nlogn)) \approx log(nlogn) = logn loglogn n \\ \to log(n!)=O(logn)[/tex]

(۱۶ شهریور ۱۳۹۱ ۱۰:۴۹ ب.ظ)hadiseh67 نوشته شده توسط:  آیا !logn محدود به چند جمله ای است؟
nlogn=logn!
من این دوتارو نفهمیدم

تو Instructor Manual کتاب CLRS حل شده