منو
 کاربر Online
793 کاربر online
تاریخچه ی: حل روابط بازگشتی ناهمگن

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!حل روابط بازگشتی ناهمگن
!!تعریف روابط بازگشتی غیرهمگن با ضرایب ثابت
رابطه بازگشتی درجه {TEX()} {k} {TEX}زیر غیر همگن است:
@@{TEX()} { a_n =c_1 a_{n -1} + \cdots + c_ka_{n -k} + f(n) } {TEX}@@
اگر An در ((رابطه بازگشتی همگن)) (1) صدق کند و{TEX()} { B_n } {TEX} در رابطه بازگشتی غیرهمگن صدق کند آنگاه {TEX()} { A_n + B_n } {TEX} نیز در رابطه غیرهمگن صدق می‌کند. زیرا:
@@{TEX()} { c_1 = (A_{n -1}+B_{n -1})+ \cdots + c_k (A_{n -k} + B_{n -k}) + f(n) = (c_1A_{n -1}+ \cdots + c_k A_{n -k})
+ (c_1 B_{n -1}+ \cdots + c_k B_{n -k} + f(n)) = A_n + B_n} {TEX}@@
در این حالت {TEX()} {A_n} {TEX}را جواب قسمت همگن رابطه و {TEX()} {B_n} {TEX}را یک جواب خاص آن گویند. مثلاً اگر
{TEX()} { a_n = 3 a_{n -1}+ 2 - 2n^2} {TEX} ، آنگاه{TEX()} { A_n = t_1 3^n } {TEX} و چون{TEX()} { f_n = 2 - 2n^2} {TEX} ، قرار میدهیم
@@{TEX()} { B_n = p n^2 +qn+r} {TEX} @@،
حال داریم:
@@{TEX()} { pn^2 + qn+ r = 3(p(n -1)^2 + q(n -1) + r) + 2 - 2n^2} {TEX}@@
در نتیجه، برای این که این رابطه یک اتحاد برای {TEX()} {n} {TEX}باشد، داریم: {TEX()} { D = 3 , C = 3 , B = 1 } {TEX}، در این صورت،{TEX()} { B_n = n^2 + 3n + 2 } {TEX} و خواهیم داشت:
@@{TEX()} { a_n = A_n + B_n = t_1 3^n + n^2 + 2 } {TEX}@@
با فرض{TEX()} { a_0 = 0 } {TEX} داریم: {TEX()} { t_1 = 1 } {TEX}پس:
@@{TEX()} { A_n = 3^n + n^2 + 3n + 2} {TEX} @@
---
!!حل روابط بازگشتی غیرهمگن
اگر رابطه بازگشتی غیرهمگن را به صورت زیر داشته باشیم:
@@(1)~~white:----------~~ {TEX()} { a¬_n = c_1 a_{n -1} + c_2 a_{n -1} + \cdots + c_k a_{n -k} + b^n P(n) } {TEX} @@
که در آن {TEX()} {b} {TEX}ثابت است و{TEX()} { P(n)} {TEX} چند جمله‌ای، از درجه {TEX()} {d} {TEX}بر حسب {TEX()} {n} {TEX}باشد، برای این رابطه، مشابه روابط بازگشتی همگن معادله سرشت‌نما به صورت زیر تعریف می‌شود:
@@ (2)~~white:----------~~ {TEX()} {x^k-c_1x^{k-1}-c_2x^{k-2}-\cdots -c^k )(x-b)^{d+1}=0} {TEX}@@
با داشتن این معادله و به دست آوردن ریشه‌های {TEX()} {(x_i)} {TEX} آن مشابه قبل، جواب‌های این معادله به صورت ترکیب خطی {TEX()} {x_i^n} {TEX} بیان می‌شود. (تحقیق این موضوع به عهده شما.) به طورکلی ریشه‌های معادله سرشت‌نمای یک رابطه بازگشتی مشخص کننده جواب‌های رابطه بازگشتی است. با داشتن این ((معادله)) سرشت‌نما برای ((روابط بازگشتی)) بسیاری از این روابط با روشی مشابه روابط بازگشتی همگن، به راحتی قابل حل است.
---
!!مثال
__ الف__. رابطه بازگشتی{TEX()} { a_n = 2a_{n -1} + (n + 5) 3^n } {TEX} را حل کنید.
__ب.__ رابطه بازگشتی{TEX()} { a_n = 2a_{n -1} + n } {TEX} را حل کنید.
__حل .__
__الف.__ معادله سرشت‌نمای این رابطه به صورت {TEX()} { (x - 2) (x -3)^2 = 0} {TEX} در می‌آید، پس: {TEX()} { a_n = t_1 2^n + t_2 3^n + t_3 n 3^n } {TEX}
که با توجه به حالت‌های اولیه داده شده، می‌توان {TEX()} {t_i} {TEX}ها را به دست آورد.
ب. معادله سرشت‌نما{TEX()} { (x -2) (x + 1)^2 = 0 } {TEX}است، پس داریم:
@@{TEX()} { a_n = t_1 2^n + t_2 + t_2 n } {TEX} @@
در حالت کلی معادله سرشت‌نمای رابطه بازگشتی زیر:
@@ (3) ~~white:----------~~ {TEX()} { a_n = c_1 a_{n -1} + c_2 a_{n -2} + \cdots + c_k a_{¬n -k} +b_1^n P_1(n)+b_2^n P_2(n) + \cdots } {TEX} @@
به صورت:
@@{TEX()} {(x^k-c_1x^{k-1}-c_2x^{k-2} -\cdots -c_k)(x-b_1)^{d_1+1} (x-b_2)^{d_2+1 }\cdots =0} {TEX}@@
است.
---
!!مثال
رابطه بازگشتی{TEX()} { a_n = 2a_{n -1} + n + 2^n } {TEX} را حل کنید.
__حل .__
معادله سرشت نمای آن به صورت {TEX()} { (x -2) (x -1)^2 (x -2) = 0 } {TEX}است. پس:
#@
@#16:
@@{TEX()} { a_n = t_1 + t_2 n + t_3 2^n + t_4 n 2^n } {TEX}@@
و مثلاً اگر{TEX()} { a_0 = 0} {TEX} داریم:
@@{TEX()} { a_n = -2 -n + 2^{n + 1} + n 2^n } {TEX}@@
بدین ترتیب بسیاری از روابط بازگشتی با ضرایب ثابت حل می‌شوند.
حال با حل مسأله‌ای کاربردی به روشی دیگر در حل روابط بازگشتی توجه می‌کنیم:
---
!!مثال. (بیست و یکمین المپیاد جهانی ریاضی)
{TEX()} {A} {TEX}و {TEX()} {E} {TEX}را دو رأس روبه‌روی یک 8 ضلعی منتظم می‌گیریم، قورباغه‌ای از رأس {TEX()} {A} {TEX}آغاز به جهیدن می‌کند و هربار به رأس مجاور می‌پرد. ولی وقتی به رأس {TEX()} {E} {TEX}رسید، همان‌جا متوقف می‌شود. {TEX()} {a_n} {TEX}را تعداد مسیرهایی می‌گیریم که قورباغه با {TEX()} {n} {TEX}جهش از {TEX()} {A} {TEX}به {TEX()} {E} {TEX}برسد. ثابت کنید:
@@{TEX()} {a_{2n}=\frac{1}{\sqrt{2}} \Big(x^{n-1}-y^{n-1} \Big)} {TEX}@@
که در آن {TEX()} {x=2+\sqrt{2}} {TEX} و {TEX()} {y=2-\sqrt{2}} {TEX}
__حل. __
8 ضلعی زیر را در نظر می‌گیریم. فرض کنید {TEX()} {b_n} {TEX}تعداد مسیرهایی باشد که قورباغه در آنها با {TEX()} {n} {TEX}جهش از {TEX()} {C} {TEX}به {TEX()} {E} {TEX}برسد. اگر قورباغه بخواهد از {TEX()} {A} {TEX}به {TEX()} {E} {TEX}برود، در دو جهش اول یا به {TEX()} {C} {TEX}می‌رسد یا به {TEX()} {G} {TEX}می‌رسد یا به {TEX()} {A} {TEX}برمی‌گردد و به دو طریق می‌تواند به {TEX()} {A} {TEX}بازگردد{TEX()} { [ABA , AHA] } {TEX} . حال از جایی که الان به آن رسیده باید شروع کند و با{TEX()} { n - 2 } {TEX}جهش به {TEX()} {E} {TEX}برسد، بنابراین{TEX()} { a_n = 2b_{n -2} + 2a_{n -2} } {TEX}. در مورد {TEX()} {b_n} {TEX}نیز مشابهاً می‌توان گفت{TEX()} { b_n = 2b_{n -2} + a_{n -2} } {TEX} (چرا؟)
::{picture=img/daneshnameh_up/1/10/com0028a.jpg}::
دقت می‌کنیم که چون بین {TEX()} {A} {TEX}و {TEX()} {E} {TEX}، 4 ضلع وجود دارد، برای رفتن از {TEX()} {A} {TEX}به {TEX()} {E} {TEX}حتماً تعداد زوجی حرکت لازم است. پس {TEX()} { a_{2n - 1} = 0} {TEX} . برای حالت‌های زوج دو رابطه بازگشتی{TEX()} { a_n = 2b_{n -2} + 2a_{n -2}} {TEX} و
{TEX()} { b_n = 2b_{n -2} + a_{n -2} } {TEX} را داریم. حال دو روش وجود دارد،
__روش اول.__ از تفاضل دو رابطه بدست می‌آید:
@@{TEX()} { b_{n -2} = a_{n -2} - a_{n -4}} {TEX}@@
و در نتیجه با گذاشتن در رابطه اولی داریم:
@@{TEX()} { a_n = 4a_{n -2} -2a_{n -4}} {TEX}@@
حال اگر {TEX()} { c_n = a_{2n} } {TEX} در نظر بگیریم، رابطه همگن{TEX()} { c_n = 4c_{n -1} -2c_{n -2} } {TEX} (به ازای{TEX()} { n > 2} {TEX}) بدست می‌آید که با توجه به حالت‌های اولیه{TEX()} { c_1 = 0 } {TEX} و{TEX()} { c_2 = 1 } {TEX} خواهیم داشت (با تشکیل معادله سرشت‌نما و حل آن بدست می‌آید):
@@{TEX()} {a_{2n}=c_n=\frac{1}{\sqrt{2}} \Big( \big(2+\sqrt{2} \big)^{n-1} -\big(2-\sqrt{2} \big)^{n-1} \Big)} {TEX}@@
حال مشابه مثال‌های قبل به دلیل اینکه {TEX()} {2-\sqrt{2}{<1} {TEX}، می‌توان تحقیق کرد:
@@ (4)~~white:---------- ~~{TEX()} {f_n=\frac{(2+\sqrt{2})^{n-1}}{\sqrt{2}}} {TEX}@@
__روش دوم. __این روش با آنچه تا به حال گفتیم متفاوت است. ما به این روش در حل این مسأله بسنده می‌کنیم:
@@{TEX()} { a_n = 2a_{n -2} + 2b_{n -2}} {TEX}@@
@@{TEX()} { b_n = a_{n -2} + 2b_{n -2}} {TEX}@@
حال اگر بردار {TEX()} {V_m} {TEX}را به صورت {TEX()} {V_m={{a_{2m}}\choose {c_{2m}}}} {TEX} تعریف کنیم، باید داشته باشیم:
@@{TEX()} {V_1={0 \choose 1} \ , \ T={{2 \quad 2}\choose {1 \quad 2}}} {TEX}@@
برای تعیین بردار {TEX()} {V_m} {TEX}با این حالت خاصیت مقادیر ویژه ماتریس {TEX()} {T} {TEX}را تعیین می‌کنیم. این مقادیر ریشه‌های معادله مفسر ((ماتریس)) می‌باشند :
@@{picture=img/daneshnameh_up/5/59/com0028b.jpg}@@
و بنابراین: {TEX()} {{\lambda}_1=2+\sqrt{2}} {TEX} و {TEX()} {{\lambda}_2=2-\sqrt{2}} {TEX} . بردارهای ویژه ماتریس {TEX()} {T} {TEX}، یعنی {TEX()} {u_1} {TEX}و {TEX()} {u_2} {TEX}دارای این ویژگی هستند که: {TEX()} {Tu_i={\lambda}_iu_i} {TEX} و{TEX()} {T(Tu_i)={\lambda}_i^2u_i} {TEX} و ……… که برای{TEX()} { i = 1 , 2} {TEX} می‌توان آنها را پیدا کرد:
@@{TEX()} {u_1=\frac{1}{\sqrt{2}}{1 \choose{\frac{1}{\sqrt{2}}}} \quad , \quad u_2=\frac{1}{\sqrt{2}} {{-1}\choose {\frac{1}{\sqrt{2}}}}} {TEX}@@
بنابراین {TEX()} {V_1} {TEX}یک ترکیب خطی از {TEX()} {u_1} {TEX}و {TEX()} {u_2} {TEX}است. یعنی:
@@{TEX()} { V_1 = {\lambda}_1 u_1 + {\lambda}_2 u_2} {TEX} @@
@@{TEX()} {\Rightarrow \ V_m=T^{(m-1)} V_1={\lambda}_1^{m-1}u_1+{\lambda}_2^{m-1}u_2={{a_{2m}}\choose {b_{2m}}}} {TEX}@@
و بدین ترتیب:
@@{TEX()} {\Rightarrow \ a_{2m}=\frac{1}{\sqrt{2}} \Big[ \big(2+\sqrt{2} \big)^{m-1} + \big(2-\sqrt{2} \big)^{m-1} \Big]} {TEX}@@

---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0049.pdf]
---
!همچنین ببینید
*((روابط بازگشتی اولیه ))
*((حل روابط بازگشتی همگن ))
#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:13 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [08:59 ]   2   زینب معزی      v  c  d  s 
 سه شنبه 14 شهریور 1385 [12:10 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..