[tex] T(n)=\frac{1}{n}\sum^n_{q=1}T[max(q-1),(n-q)]+n=\frac{2}{n}\sum^{n-1}_{q=n/2}T(q)+n[/tex]رابطه#۱
[tex]nT(n)\: -(n-1)T(n-1)\: =2\sum_{q=n/2}^{n-1}T(q)+n^2\: -\: 2\sum_{q=n-1/2}^{n-2}T(q)\: -\: (n-1)^2[/tex] رابطه#۲
[tex] nT(n)\: -(n-1)T(n-1)\: =2\sum_{q=n-1/2}^{n-2}T(q)+2T(n-1)+n^2\: -\: 2\sum_{q=n-1/2}^{n-2}T(q)\: -\: (n-1)^2[/tex] رابطه # ۳
سلام .توی این رابطه بازگشتی.رابطه #۲رو برای اینکه سیگمای سمت چپ رو معادل سیگمای سمت راست کنیم.(باید کرانهای هر دو سیگما یکی شوند تا
بتونیم اونها رو از هم کم کنیم).برای اینکه سیگمای سمت چپ معادل سمت راستی بشه (کران بالا و پایین اون رو باید منهای[tex](n-1)[/tex] کنیم.)
(نتیجه در رابطه # ۳ )حالا با این تغییر سیگما میدونم که باید دو جمله به سری اضافه بشه یکی[tex]2T(n-1)[/tex] بخاطر کران بالا و یک جمله هم باید کم بشه برای اینکه کران پایین رو از یکی کمتر شروع کردیم .حالا مشکل اینجاست که هر عبارتی رو که از سری کم میکنم جواب نمیده ؟!!! لطفا راهنمایی کنید . ممنونم