تاریخچه ی:
استقرای چندگانه
تفاوت با نگارش: 1
| | ||V{maketoc}|| | | ||V{maketoc}|| |
| | ^@#16: | | ^@#16: |
| | !استقرای چند گانه | | !استقرای چند گانه |
| | در بعضی از مسایل استقرایی، برای اثبات گام استقرایی مساله{TEX()} { A } {TEX} ، به اثبات مساله{TEX()} { B } {TEX} احتیاج پیدا می کنیم و برای اثبات گام استقرایی مساله{TEX()} { B } {TEX} ، به اثبات مساله{TEX()} { A } {TEX} احتیاج پیدا می کنیم. به نظر می رسد که دور اتفاق می افتد و نمی توانیم هیچ کدام از مسایل را اثبات کنیم. ولی گاهی برای اثبات{TEX()} {A(n+1)} {TEX}، به درستی {TEX()} {A(n)} {TEX} و {TEX()} {B(n)} {TEX} نیاز داریم و برای اثبات {TEX()} {B(n+1)} {TEX} به {TEX()} {A(n+1)} {TEX} و {TEX()} {B(n)} {TEX} احتیاج داریم. در این گونه موارد دور اتفاق نمی افتد و می توانیم از استقرا استفاده کنیم زیرا، درستی {TEX()} {B(1)} {TEX}و {TEX()} {A(1)} {TEX}، درستی {TEX()} {A(2)} {TEX} را نتیجه می دهند و بعد درستی {TEX()} {B(1)} {TEX}و {TEX()} {A(2)} {TEX} درستی {TEX()} {B(2)} {TEX} را نتیجه می دهند. سپس درستی {TEX()} {B(2)} {TEX}و {TEX()} {A(2)} {TEX} درستی {TEX()} {A(3)} {TEX} را نتیجه می دهند و حالا درستی {TEX()} {B(2)} {TEX}و {TEX()} {A(3)} {TEX}، درستی {TEX()} {B(3)} {TEX} را نتیجه می دهند و ... بدین ترتیب به راحتی هر دو مساله{TEX()} { B } {TEX} و{TEX()} { A } {TEX} ، اثبات می شوند. حال به بررسی چند مثال می پردازیم. | | در بعضی از مسایل استقرایی، برای اثبات گام استقرایی مساله{TEX()} { A } {TEX} ، به اثبات مساله{TEX()} { B } {TEX} احتیاج پیدا می کنیم و برای اثبات گام استقرایی مساله{TEX()} { B } {TEX} ، به اثبات مساله{TEX()} { A } {TEX} احتیاج پیدا می کنیم. به نظر می رسد که دور اتفاق می افتد و نمی توانیم هیچ کدام از مسایل را اثبات کنیم. ولی گاهی برای اثبات{TEX()} {A(n+1)} {TEX}، به درستی {TEX()} {A(n)} {TEX} و {TEX()} {B(n)} {TEX} نیاز داریم و برای اثبات {TEX()} {B(n+1)} {TEX} به {TEX()} {A(n+1)} {TEX} و {TEX()} {B(n)} {TEX} احتیاج داریم. در این گونه موارد دور اتفاق نمی افتد و می توانیم از استقرا استفاده کنیم زیرا، درستی {TEX()} {B(1)} {TEX}و {TEX()} {A(1)} {TEX}، درستی {TEX()} {A(2)} {TEX} را نتیجه می دهند و بعد درستی {TEX()} {B(1)} {TEX}و {TEX()} {A(2)} {TEX} درستی {TEX()} {B(2)} {TEX} را نتیجه می دهند. سپس درستی {TEX()} {B(2)} {TEX}و {TEX()} {A(2)} {TEX} درستی {TEX()} {A(3)} {TEX} را نتیجه می دهند و حالا درستی {TEX()} {B(2)} {TEX}و {TEX()} {A(3)} {TEX}، درستی {TEX()} {B(3)} {TEX} را نتیجه می دهند و ... بدین ترتیب به راحتی هر دو مساله{TEX()} { B } {TEX} و{TEX()} { A } {TEX} ، اثبات می شوند. حال به بررسی چند مثال می پردازیم. |
| | می دانیم دنباله {TEX()} {1,1,2,3,5,8,13,21,34,55,\cdots } {TEX} که هر جمله با شروع از جمله سوم، برابر مجموع دو جمله قبلی آن است را دنباله فیبوناتچی می نامیم. اگر {TEX()} {F_n} {TEX}، جمله {TEX()} { n } {TEX} ام فیبوناتچی باشد؛ می توانیم دنباله فیبوناتچی را با رابطه بازگشتی زیر نشان دهیم: | | می دانیم دنباله {TEX()} {1,1,2,3,5,8,13,21,34,55,\cdots } {TEX} که هر جمله با شروع از جمله سوم، برابر مجموع دو جمله قبلی آن است را دنباله فیبوناتچی می نامیم. اگر {TEX()} {F_n} {TEX}، جمله {TEX()} { n } {TEX} ام فیبوناتچی باشد؛ می توانیم دنباله فیبوناتچی را با رابطه بازگشتی زیر نشان دهیم: |
| | @@{picture=img/daneshnameh_up/9/9e/comm0006aJPG.JPG} @@ | | @@{picture=img/daneshnameh_up/9/9e/comm0006aJPG.JPG} @@ |
| - | در قسمت روابط بازگشتی به بررسی دنباله فیبوناتچی می پردازیم. در اینجا نیز یک مساله در مورد دنباله فیبوناتچی را بررسی می کنیم. |
+ | در قسمت روابط بازگشتی به بررسی دنباله ((فیبوناتچی)) می پردازیم. در اینجا نیز یک مساله در مورد دنباله فیبوناتچی را بررسی می کنیم. |
| | --- | | --- |
| - | !مثال |
+ | !!مثال |
| | فرض کنید{TEX()} {F_i} {TEX}،{TEX()} { i } {TEX} امین جمله ی فیبوناتچی باشد. به ازای هر{TEX()} {n\in N} {TEX} ثابت کنید: | | فرض کنید{TEX()} {F_i} {TEX}،{TEX()} { i } {TEX} امین جمله ی فیبوناتچی باشد. به ازای هر{TEX()} {n\in N} {TEX} ثابت کنید: |
| | @@{TEX()} {F_{n+1}^2+F_n^2=F_{2n+1}} {TEX}@@ | | @@{TEX()} {F_{n+1}^2+F_n^2=F_{2n+1}} {TEX}@@ |
| | __اثبات__ | | __اثبات__ |
| | حکم به ازای{TEX()} { n = 1} {TEX} برقرار است زیرا،{TEX()} {F_3=2=1+1=F_1+F_2} {TEX}. حال فرض کنید که مساله به ازای{TEX()} { n = k } {TEX} درست باشد، یعنی{TEX()} {F_{k+1}^2+F_k^2=F_{2k+1}} {TEX}. می خواهیم مساله را به ازای{TEX()} { n = k + 1 } {TEX} ثابت کنیم. داریم: | | حکم به ازای{TEX()} { n = 1} {TEX} برقرار است زیرا،{TEX()} {F_3=2=1+1=F_1+F_2} {TEX}. حال فرض کنید که مساله به ازای{TEX()} { n = k } {TEX} درست باشد، یعنی{TEX()} {F_{k+1}^2+F_k^2=F_{2k+1}} {TEX}. می خواهیم مساله را به ازای{TEX()} { n = k + 1 } {TEX} ثابت کنیم. داریم: |
| | @@{TEX()} {F_{k+2}^2+F_{k+1}^2=(F_{k+1}+F_k)^2+F_{k+1}^2=(F_{k+1}^2+F_k^2)+2F_{k+1}F_k+F_{k+1}^2=F_{2k+1}+2F_{k+1}F_k+F_{k+1}^2} {TEX}@@ | | @@{TEX()} {F_{k+2}^2+F_{k+1}^2=(F_{k+1}+F_k)^2+F_{k+1}^2=(F_{k+1}^2+F_k^2)+2F_{k+1}F_k+F_{k+1}^2=F_{2k+1}+2F_{k+1}F_k+F_{k+1}^2} {TEX}@@ |
| | اگر بخواهیم حکم مساله درست باشد باید داشته باشیم: | | اگر بخواهیم حکم مساله درست باشد باید داشته باشیم: |
| | @@{TEX()} {F_{2k+1}+2F_{k+1}F_k+F_{k+1}^2=F_{2k+3}} {TEX}@@ | | @@{TEX()} {F_{2k+1}+2F_{k+1}F_k+F_{k+1}^2=F_{2k+3}} {TEX}@@ |
| | و با توجه به این که{TEX()} {F_{2k+3}=F_{2k+2}+F_{2k+1}} {TEX}، باید ثابت کنیم: | | و با توجه به این که{TEX()} {F_{2k+3}=F_{2k+2}+F_{2k+1}} {TEX}، باید ثابت کنیم: |
| | @@{TEX()} {2F_{k+1}F_k+F_{k+1}^2=F_{2k+2}} {TEX}@@ | | @@{TEX()} {2F_{k+1}F_k+F_{k+1}^2=F_{2k+2}} {TEX}@@ |
| | پس بیایید مساله ی بالا را، با کمک استقرا، ثابت کنیم. حکم به ازای{TEX()} { n = 1} {TEX} بدیهی است زیرا | | پس بیایید مساله ی بالا را، با کمک استقرا، ثابت کنیم. حکم به ازای{TEX()} { n = 1} {TEX} بدیهی است زیرا |
| | @@{TEX()} {2F_2F_1+F_2^2=2+1=3=F_4} {TEX}.@@ | | @@{TEX()} {2F_2F_1+F_2^2=2+1=3=F_4} {TEX}.@@ |
| | حال فرض کنید که مساله ی دوم به ازای{TEX()} { n = k } {TEX} برقرار باشد یعنی{TEX()} {2F_{k+1}F_k+F_{k+1}^2=F_{2k+2}} {TEX}؛ پس داریم: | | حال فرض کنید که مساله ی دوم به ازای{TEX()} { n = k } {TEX} برقرار باشد یعنی{TEX()} {2F_{k+1}F_k+F_{k+1}^2=F_{2k+2}} {TEX}؛ پس داریم: |
| | @@{TEX()} {2F_{k+2}F_{k+1}+F_{k+2}^2=2(F_{k+1}+F_k)F_{k+1}+F_{k+2}^2=(F_{k+1}^2+2F_{k+1}F_k)+F_{k+1}^2+F_{k+2}^2=F_{2k+2}+F_{k+1}^2+F_{k+2}^2} {TEX}@@ | | @@{TEX()} {2F_{k+2}F_{k+1}+F_{k+2}^2=2(F_{k+1}+F_k)F_{k+1}+F_{k+2}^2=(F_{k+1}^2+2F_{k+1}F_k)+F_{k+1}^2+F_{k+2}^2=F_{2k+2}+F_{k+1}^2+F_{k+2}^2} {TEX}@@ |
| | اگر بخواهد حکم استقرا درست باشد باید داشته باشیم: | | اگر بخواهد حکم استقرا درست باشد باید داشته باشیم: |
| | @@{TEX()} {F_{2k+2}+F_{k+1}^2+F_{k+2}^2=F_{2k+4}} {TEX}@@ | | @@{TEX()} {F_{2k+2}+F_{k+1}^2+F_{k+2}^2=F_{2k+4}} {TEX}@@ |
| | و با توجه به این که{TEX()} {F_{2k+4}=F_{2k+3}+F_{2k+2}} {TEX}، باید داشته باشیم: {TEX()} {F_{2k+3}=F_{k+1}^2+F_{k+2}^2} {TEX}. این همان مساله ی قبلی است. لذا دو مساله به یکدیگر وابسته شده اند و درستی اولی به درستی دومی و درستی دومی به درستی اولی وابسته است. | | و با توجه به این که{TEX()} {F_{2k+4}=F_{2k+3}+F_{2k+2}} {TEX}، باید داشته باشیم: {TEX()} {F_{2k+3}=F_{k+1}^2+F_{k+2}^2} {TEX}. این همان مساله ی قبلی است. لذا دو مساله به یکدیگر وابسته شده اند و درستی اولی به درستی دومی و درستی دومی به درستی اولی وابسته است. |
| | اگر قرار دهیم: | | اگر قرار دهیم: |
| | @@{TEX()} {P(n) \ : \ F_{n+1}^2+F_n ^2 =F_{2n+1}} {TEX}@@ | | @@{TEX()} {P(n) \ : \ F_{n+1}^2+F_n ^2 =F_{2n+1}} {TEX}@@ |
| | @@{TEX()} {Q(n) \ : \ 2F_{n+1}F_n+F_{n+1}^2=F_{2n+2}} {TEX}@@ | | @@{TEX()} {Q(n) \ : \ 2F_{n+1}F_n+F_{n+1}^2=F_{2n+2}} {TEX}@@ |
| | با توجه به استدلال های بالا نتیجه می گیریم که: درستی{TEX()} { P(n) } {TEX}و{TEX()} { Q(n) } {TEX}، درستی{TEX()} { P(n + 1) } {TEX}را نتیجه می دهد و درستی{TEX()} { P(n + 1) } {TEX}و{TEX()} { Q(n) } {TEX}درستی {TEX()} { Q(n + 1) } {TEX} را نتیجه می دهد. حال با توجه به مطالبی که در ابتدای این بخش گفته شد، اثبات کامل است. | | با توجه به استدلال های بالا نتیجه می گیریم که: درستی{TEX()} { P(n) } {TEX}و{TEX()} { Q(n) } {TEX}، درستی{TEX()} { P(n + 1) } {TEX}را نتیجه می دهد و درستی{TEX()} { P(n + 1) } {TEX}و{TEX()} { Q(n) } {TEX}درستی {TEX()} { Q(n + 1) } {TEX} را نتیجه می دهد. حال با توجه به مطالبی که در ابتدای این بخش گفته شد، اثبات کامل است. |
| | !!مثال | | !!مثال |
| | فرض کنید{TEX()} {S_{n,0}} {TEX}،{TEX()} {S_{n,1}} {TEX} و{TEX()} {S_{n,2}} {TEX} مجموع دو جمله در میان عنصرهای سطر{TEX()} { n } {TEX} ام مثلث خیام باشند که به ترتیب با اولین، دومین و سومین عنصر از سمت چپ آغاز می شوند. روابط زیر را ثابت کنید. | | فرض کنید{TEX()} {S_{n,0}} {TEX}،{TEX()} {S_{n,1}} {TEX} و{TEX()} {S_{n,2}} {TEX} مجموع دو جمله در میان عنصرهای سطر{TEX()} { n } {TEX} ام مثلث خیام باشند که به ترتیب با اولین، دومین و سومین عنصر از سمت چپ آغاز می شوند. روابط زیر را ثابت کنید. |
| | @@{TEX()} {P_0(k) \ : \ S_{6k,0}-1=S_{6k,1}=S_{6k,2}} {TEX}@@ | | @@{TEX()} {P_0(k) \ : \ S_{6k,0}-1=S_{6k,1}=S_{6k,2}} {TEX}@@ |
| | @@{TEX()} {P_1(k) \ : \ S_{6k+1,0}=S_{6k+1,1} =S_{6k+1,2}+1} {TEX}@@ | | @@{TEX()} {P_1(k) \ : \ S_{6k+1,0}=S_{6k+1,1} =S_{6k+1,2}+1} {TEX}@@ |
| | @@{TEX()} {P_2(k) \ : \ S_{6k+2,0}=S_{6k+3,1}=S_{6k+2,2}} {TEX}@@ | | @@{TEX()} {P_2(k) \ : \ S_{6k+2,0}=S_{6k+3,1}=S_{6k+2,2}} {TEX}@@ |
| | @@{TEX()} {P_3(k) \ : \ S_{6k+3,0}+1=S_{6k+3,1}=S_{6k+3,2}} {TEX}@@ | | @@{TEX()} {P_3(k) \ : \ S_{6k+3,0}+1=S_{6k+3,1}=S_{6k+3,2}} {TEX}@@ |
| | @@{TEX()} {P_4(k) \ : \ S_{6k+4,0}=S_{6k+4,1}=S_{6k+4,2}-1} {TEX}@@ | | @@{TEX()} {P_4(k) \ : \ S_{6k+4,0}=S_{6k+4,1}=S_{6k+4,2}-1} {TEX}@@ |
| | @@{TEX()} {P_5(k) \ : \ S_{6k+5,0}=S_{6k+5,1}+1=S_{6k+5,2}} {TEX}@@ | | @@{TEX()} {P_5(k) \ : \ S_{6k+5,0}=S_{6k+5,1}+1=S_{6k+5,2}} {TEX}@@ |
| | __اثبات__ | | __اثبات__ |
| | حکم را به این صورت نتیجه می گیریم که | | حکم را به این صورت نتیجه می گیریم که |
| | @@{TEX()} {P_0(k) \ \Rightarrow \ P_1(k)\qquad (1)} {TEX}@@ | | @@{TEX()} {P_0(k) \ \Rightarrow \ P_1(k)\qquad (1)} {TEX}@@ |
| | @@{TEX()} {P_1(k) \ \Rightarrow \ P_2(k) \qquad (2)} {TEX}@@ | | @@{TEX()} {P_1(k) \ \Rightarrow \ P_2(k) \qquad (2)} {TEX}@@ |
| | @@{TEX()} {P_2(k) \ \Rightarrow \ P_3(k) \qquad (3)} {TEX}@@ | | @@{TEX()} {P_2(k) \ \Rightarrow \ P_3(k) \qquad (3)} {TEX}@@ |
| | @@{TEX()} {P_3(k) \ \Rightarrow \ P_4(k) \qquad (4)} {TEX}@@ | | @@{TEX()} {P_3(k) \ \Rightarrow \ P_4(k) \qquad (4)} {TEX}@@ |
| | @@{TEX()} {P_4(k) \ \Rightarrow \ P_5(k) \qquad (5)} {TEX}@@ | | @@{TEX()} {P_4(k) \ \Rightarrow \ P_5(k) \qquad (5)} {TEX}@@ |
| | @@{TEX()} {P_5(k) \ \Rightarrow \ P_0(k+1) \qquad (6)} {TEX}@@ | | @@{TEX()} {P_5(k) \ \Rightarrow \ P_0(k+1) \qquad (6)} {TEX}@@ |
| | برای نتیجه گیری روابط بالا کافی است دقت کنیم که | | برای نتیجه گیری روابط بالا کافی است دقت کنیم که |
| | @@{TEX()} {S_{n,0}=S_{n-1,2}+S_{n-1,0} \qquad (7)} {TEX}@@ | | @@{TEX()} {S_{n,0}=S_{n-1,2}+S_{n-1,0} \qquad (7)} {TEX}@@ |
| | @@{TEX()} {S_{n,1}=S_{n-1,0}+S_{n-1,1} \qquad (8)} {TEX}@@ | | @@{TEX()} {S_{n,1}=S_{n-1,0}+S_{n-1,1} \qquad (8)} {TEX}@@ |
| | @@{TEX()} {S_{n,2}=S_{n-1,1}+S_{n-1,2} \qquad (9)} {TEX}@@ | | @@{TEX()} {S_{n,2}=S_{n-1,1}+S_{n-1,2} \qquad (9)} {TEX}@@ |
| | و درستی روابط (9) , (8) , (7) از این جا ناشی می شود که هر عنصر در مثلث خیام، برابر با مجموع دو عنصر بالایی آن است. با توجه به این روابط به راحتی روابط (1) تا (6) ثابت می شوند، در نتیجه حکم مساله ثابت می گردد. | | و درستی روابط (9) , (8) , (7) از این جا ناشی می شود که هر عنصر در مثلث خیام، برابر با مجموع دو عنصر بالایی آن است. با توجه به این روابط به راحتی روابط (1) تا (6) ثابت می شوند، در نتیجه حکم مساله ثابت می گردد. |
| - | |
+ | ---
!پیوندهای خارجی
[http://olympiad.roshd.ir/computer/content/pdf/0004.pdf]
---
!همچنین ببینید
*((استقرای قوی))
*((استقرای قوی و چندگانه )) |
| | #@^ | | #@^ |
