منو
 کاربر Online
1061 کاربر online
تاریخچه ی: استقرای چندگانه

||V{maketoc}||
^@#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()} {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} @@
در قسمت روابط بازگشتی به بررسی دنباله فیبوناتچی می پردازیم. در اینجا نیز یک مساله در مورد دنباله فیبوناتچی را بررسی می کنیم.
---
!!مثال
فرض کنید{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()} { 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_{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()} {2F_{k+1}F_k+F_{k+1}^2=F_{2k+2}} {TEX}@@
پس بیایید مساله ی بالا را، با کمک استقرا، ثابت کنیم. حکم به ازای{TEX()} { n = 1} {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()} {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+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()} {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()} {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_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_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_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_1(k) \ \Rightarrow \ P_2(k) \qquad (2)} {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_4(k) \ \Rightarrow \ P_5(k) \qquad (5)} {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,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}@@
و درستی روابط (9) , (8) , (7) از این جا ناشی می شود که هر عنصر در مثلث خیام، برابر با مجموع دو عنصر بالایی آن است. با توجه به این روابط به راحتی روابط (1) تا (6) ثابت می شوند، در نتیجه حکم مساله ثابت می گردد.

#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 پنج شنبه 16 شهریور 1385 [13:44 ]   3   زینب معزی      جاری 
 دوشنبه 26 تیر 1385 [09:11 ]   2   فرید امیرغیاثوند      v  c  d  s 
 دوشنبه 26 تیر 1385 [09: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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..