: حل روابط بازگشتی ناهمگن

||V{maketoc}||

^@#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]

---

!همچنین ببینید

*((روابط بازگشتی اولیه ))