||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]

#@^