| - | برهان: برای اثبات از برهان خلف کمک می گیریم. به برهان خلف فرض می کنیم با مفروضات فوق مجموعه S برابر مجموعه اعداد طبیعی نباشد. پس مجموعه ای چون T وجود دارد که S=N-T. حال داریم: مجموعه T زیر مجموعه اعداد طبیعی است و ناتهی است(چرا؟) پس بنا بر اصل خوشترتیبی T دارا عضو مینیمم است چون{TEX()} {t_0} {TEX} واضح است که {TEX()} {t_0\ne\ 1} {TEX} و چون {TEX()} {1\in S} {TEX} پس داریم:{TEX()} {t_0-1<t_0} {TEX} و چون {TEX()} {t_0} {TEX} برابر مینیمم مجموعه T است پس {TEX()} {t_0-1\in S} {TEX} و لذا از شرط دوم مجموعه S داریم:{TEX()} {t_0-1\in S \Rightarrow\ (t_0-1)+1\in S\Rightarrow\ t_0\in S} {TEX}
که این تناقض است چون {TEX()} {t_0\in T} {TEX} پس فرض خلف باطل و حکم(اصل اسقرا) برقرار است.
!اصل استقرای ریاضی ه ه ا سیم ی ود:
!!اصل استقرای معمولی یا عیف:
مابق این ال اگر (P(n حکمی برای مموعه ای ا اعداد طبیعی باد، و P برای n=1 درست باشد و ا درستی (P(k (فرض استقرا) انیم به رستی (P(k+1 برسیم. در این صورت به این نیه می رسیم که که حکم (P(n برای تمام اعدا طبیعی درست است.
------------------------------------------
!!اصل استقرای قوی ریاضی:
این اصل بیان یکد اگر S زیر مجموعه ای از اعداد طبیعی باشد به گونه ی که:
1){TEX()} {1\in S} {TEX}
2) اگر اعداد طبیعی کوچکتر از n عضو S باشند انگاه بتوان نتیجه گرت n هم عضوی از S است
می توا گف مجموعه S همان مجموعه اعداد طبیعی است.
------------------------------------------
!!ال استقرای تعمیم یافته: |
+ | ^@#12:این اصل بیان میکند اگر S زیرمجموعه ای ناتهی از ((اعداد طبیعی)) باشد به طوری که: />1) عدد یک عضو این مجموعه باشد. {TEX()} {1\in S} {TEX}
2) هرگاه عدد طبیعی __n__ در مجموعه S باشد آنگاه __n+1__ نیز عضو این مجموعه باشد.{TEX()} {\forall n\in N: n\in S \Rightarrow\ n+1\in S} {TEX}
میتوان تنیجه گرفت هر عدد طبیعی عضو S است و به عبارت دیگر S همان مجموعه اعداد طبیعی است.#@^
---
*~~purple:لازم به توضیح است این اصل با پذیرش ((اصل خوش ترتیبی)) قابل اثبات است.~~
^__~~green:@#16:برهان:#@~~__
@#12:برای اثبات از برهان خلف کمک می گیریم. به برهان خلف فرض می کنیم با مفروضات فوق مجموعه S برابر مجموعه اعداد طبیعی نباشد. پس مجموعه ای چون T وجود دارد که S=N-T. حال داریم: مجموعه T زیر مجموعه اعداد طبیعی است و ناتهی است(چرا؟) پس بنا بر اصل خوشترتیبی T دارا عضو مینیمم است چون#@{TEX()} {t_0} {TEX} @#12:واضح است که#@ {TEX()} {t_0\ne\,1} {TEX} @#12:و چون#@ {TEX()} {1\in S} {TEX} @#12:پس داریم:#@{TEX()} {t_0-1<t_0} {TEX} @#12:و چون #@{TEX()} {t_0} {TEX} @#12:برابر مینیمم مجموعه T است پس #@{TEX()} {t_0-1\in S} {TEX} @#12:و لذا از شرط دوم مجموعه S داریم:#@{TEX()} {t_0-1\in S \Rightarrow\,(t_0-1)+1\in S\Rightarrow\,t_0\in S} {TEX}
@#12:که این تناقض است چون#@ {TEX()} {t_0\in T} {TEX} @#12:پس فرض خلف باطل و حکم(اصل اسقرا) برقرار است#@.^
---
*به این ترتیب برای اثبات برخی از مسائل و احکام ریاضی که درباره اعداد __طبیعی__ می باشند می توان از اصل استقرای ریاضی ستفاده کد که ابات ب ی روش، یک روش مستقیم در استدال ریاضی ست.
---
__~~orange:@#16:صورتی دیگر از اصل استقرای ریاضی:(اثبات به کمک اصل استقرای ریاضی)#@~~ __
همان گونه که گفته شد از اصل استقرا برای اثبات احکامی در مورد اعداد طبیعی استفاده می شود. حال روش اثبات را بوسیله این اصل یان می کنیم:
^@#12:اگر __(P(n__ حکمی در مورداعداد طبیعی باشد __(P(n__ برای هر عدد طبیعی __n__ درست است اگر و فقط اگر:
1- حکم __(P(1__ رست باشد. به عبارت دیگر حکم برای __n=1__ برقرار باشد. (این مرحله را محله مبنای استقرا می گوییم.)
2- به ازای هر عدد طبیعی __k__ از فرض درستی __(P(k__ (فرض استقرا) بتوان درستی __(P(k+1__ (حکم استقرا) را نتیجه گرفت.#@^
به عبارت دیگر نشان می دهیم دد 1 در دامنه حکم است و چون هر k طبیعی که در دامنه حکم باشد k+1 هم در دامنه است می توان گف دامنه حکم هر عدد طبیعی است و هر عدد طبیعی در حکم صدق می کند.
*~~purple: لازم به توضیح ات که د اثبات به کمک اصل استقرا هر ک دو شرط فوق باید برقرار باشد تا بتوان درستی حکم را نتیجه گرفت.~~
---
~~red:__مثال:__~~ نشان دهید برای هر عدد طبیعی n: {TEX()} {4+9+14+...+(5n-1)=\frac{n(5n+3)}{2}} {TEX}
~~green:پاسخ:~~ اثبات را با استفاده از اصل استقرای ریاضی انجام می دهیم:
1- درستی حکم داده شده را برای n=1 بررسی می کنیم: (مرحله مبنایی استقرا)
سمت راست تساوی: 4
سمت چپ تساوی: {TEX()} {n=1: \farc{1(5(1)+3)}{2}\ =4} {TEX}
پس برای n=1 طرفین تساوی دادهشده با هم برابر می شوند که نشان می هد حکم برای n=1 درست است.
2- فرض می کنیم تساوی داده شده به ازای عدد طبیعی n=k برقرار باشد(فرض استقرا) ینی:
{TEX()} {n=k: 4+9+14+...+(5k-1)=\frac{k(5k+3)}{2}} {TEX}
نشان میدهیم حکم برای n=k+1 هم رقرار است(حکم استقرا) یعنی: />{TEX()} {n=k+1: 4+9+14+...+(5k-1)+(5(k+1)-1)=\frac{(k+1)(5k+8)}{2}} {TEX}
برای اثبات حکم استقرا از فرض استقرا کمک می گیریم. برای این کار به طرفین فرض استقرا عبارت {TEX()} {5k+4} {TEX} را اضافه میکنیم:
{TEX()} {4+9+14+...+(5k-1)+(5k+4)=\frac{k(5k+3)}{2}\ +(5k+4)} {TEX}
حال در سمت راست تساوی فوق داریم:
{TEX()} {\frac{k(5k+3)}{2}\ +(5k+4)\ =\frac{(5k^2+3k+10k+8)}{2} \ =\frac{(5k^2+5k+8k+8)}{2}} {TEX}
{TEX()} {=\frac{5k(k+1)+8(k+1)}{2}\ =\frac{(k+1)(5k+8)}{2}} {TEX}
پس نشان داده شد:{TEX()} {4+9+14+...+(5k-1)+(5k+4)=\frac{(k+1)(5k+8)}{2}} {TEX}
به این ترتیب بر طبق اصل استقرا حکم فوق برای هر n عضو اعداد طبیعی برقرار است. />---
__~~orange:@#16:اصل استقراء تعمیم یافــته:#@~~__
گاهی ممکن است با احکامی روبه رو شویم که برای n=1 برقرار نمی باشن و بای در بررسی شرط اول (مرحله مبنا) از عددی طبیعی بزرگتر استفاده کنیم به این ترتیب از اصل استقراء تعمیم یافــته استفاده می کنیم.
^@#12:~~green:اصل استقرای تعمیم یافته:~~
اگر __(P(n__حکمی در باره اعداد طبیعی __n__ (یا صحیح) باشد در صورتی که:
1- برای هر عدد طبیعی __P(m) ، m>1__ درست باشد
2- به ازای هر عدد طبیعی {TEX()} {k\ge\,m} {TEX}، از درستی __(P(k__ درستی __(P(k+1__ نتیجه شود
آنگاه میتوان گفت حکم __(P(n__ برای هر عدد طبیعی {TEX()} {n\ge\,m} {TEX} برقرار است.#@^
* ~~purple:به این ترتیب در اثبات مسائل به کمک اصل استقرای تعمیم یافته باید m مناسب را برای بررسی شرط اول بیابیم.~~
---
~~red:__مثال:__~~ نشان دهید عدد طبیعی مناسبی مانند m وجود دارد که برای هر عدد طبیعی n بزرگتر یا مساوی m داریـم: {TEX()} {2n+1<2^n} {TEX}
~~green:پاسخ:~~ با قرار دادن مقادیر طبیعی برای m متوجه می شویم که m مناسب 3 است چرا که برای اولین بار حکم برای m=3 درست است. حال نشان میدهیم حکم برای هر عدد طبیعی {TEX()} {m\ge 3} {TEX} برقرار است.
@#13:1-#@ {TEX()} {n=3: 2(3)+1<2^3\Rightarrow\ 7<8\>(true)} {TEX}
2- اکنون در این مرحله فرض (فرض استقرا) می کنیم نامساوی فوق برای هر عدد طبیعی {TEX()} {k\ge 3} {TEX} درست باشد یعنی: {TEX()} {k\ge 3: 2k+1<2^k} {TEX}
نشان میدهیم حکم داده شده برای (n=k+1 ،(k>2 درست است، یعنی:
{TEX()} {n=k+1, (k\ge 3): 2k+3<2^{k+1}} {TEX} (حکم استقرا)
برای این منظور از فرض استقرا استفاده کرده و به طرفین فرض عدد 2 را اضافه می کنیم، داریم:
{TEX()} {2k+1<2^k \Rightarrow\ 2k+3<2^k+2 } {TEX}
حال با مقایسه نامساوی اخیر و حکم استقرا کافی است نشان دهیم:
{TEX()} {2^k+2<2^{k+1}} {TEX}
برای این کار از اثبات بازگشتی کمک میگیریم:
{TEX()} {2^k+2<2^{k+1}\Rightarrow \ 2<2^k\times 2\ -2^k\Rightarrow \ 2<2^k(2-1)\Rightarrow \ 2<2^k} {TEX}
مشاهده می شود نامساوی {TEX()} {2<2^k} {TEX} برای K>2 همواره درست است و چون تمامی روابط برگشت پذیرند، لذا {TEX()} {2^k+2<2^{k+1}} {TEX} برقرار بوده و به این ترتیب حکم برای هر عدد طبیعی {TEX()} {n\ge 3} {TEX} برقرار است.
---
*~~purple:لازم به توضیح است که از اصل استقرای ریاضی میتوان در اثبات برخی قضایای هندسه نیز استفاده نمود.~~
---
__~~red:مثال:~~__ نشان دهید در هر n ضلعی محدب تعداد قطرها برابر است با: {TEX()} {\frac{n(n-3)}{2}} {TEX}
~~green:پاسخ:~~ می دانیم یک 3 ضلعی محدب، ((مثلث)) دارای هیچ قطری نمی باشد و چهار ضلعی محدب دارای
دو قطر است. به این ترتیب حکم را برای n>3 اثبات می کنیم. مرحله اول (مبنا) را با n=4 آغاز می کنیم:
@#13:1-#@ {TEX()} {n=4: \frac{4(4-3)}{2}\ =2 ,(true)} {TEX}
حال فرض می کنیم که حکم برای n=k درست باشد، یعنی تعداد قطرهای هر k ضلعی محدب برابر باشد با:
{TEX()} {n=k:\frac{k(k-3)}{2}} {TEX}
نشان می دهیم که حکم برای n=k+1 هم درست است، یعنی تعداد قطرهای هر k+1 ضلعی محدب برابر است با:
{TEX()} {n=k+1:\frac{(k+1)(k-2)}{2}} {TEX}
برای اثبات سعی می کنی به گونه ای از فرض استقرا استفاده کنیم. به این صورت که می دانیم که اگر به تعداد ضلعهای یک n ضلعی، یک ضلع اضافه کنیم یا به تعداد رئوس آن یک راس اضافه کنیم به تعداد قطرهای آن n-1 واحد اضافه می شود. لذا:
::__(k-1)+تعداد قطرهای k ضلعی محدب=تعداد قطرهای k+1 ضلعی محدب__::
بنابراین رابطه زیر برقرار است:
::{TEX()} {=\frac{k(k-3)}{2}\ +(k-1)} {TEX} تعداد قطرهای k+1 ضلعی محدب::
::{TEX()} {=\frac{k^2-k-2}{2}\ =\frac{(k+1)(k-2)}{2}} {TEX}::
و لذا حکم برای هر n>3 برقرار است.
---
__@#16:~~orange:اصل استقرای قوی ریاضی:~~#@__
صورتی دیگر از اصل استقرای ریاضی به شکل زیر مطرح می شود، که به اصل استقرای قوی ریاضی موسوم است. این اصل با اصل استقرای ریاضی و در نتیجه با ((اص خوش ترتیبی)) عادل است.
^@#12:~~green:اصل استقرای قوی ریاضی:~~
اگر __S__ زیرمجموعه ای از اعداد طبیعی باشد، به طوی که:
1- عدد یک عضوی از مجموعه __S__ باشد. {TEX()} {1\in S} {TEX}
2- اگر اعداد طبیعی کوچکتر از __n__ در مجموعه __S__ باشند، آنگاه __n__ نیز عضو __S__ باشد
در این صورت هر عدد طبیعی عضوی از __S__ است و به عبارت دیگر __S__ همان مجموعه اعداد طبیعی است.#@^
*~~purple:لازم به تذر است ر ریاضیات برای اثبات احکام طبیعی بیشتر از اصل استقرای قوی ریاضی استفاده میشود.~~
---
__~~orange:روش اثبات احکام بوسیله اصل استقرای قوی ریاضی:~~__
^@#12:مراحل اثبات به کمک اصل استقرای قوی ریاضی به این صورت است:
1- درستی حکم را برای __n=1__ بررسی می کنیم.
2- نشان می دهیم که اگر حکم داده شده به ازا هر عدد طبیعی __k__ که __(k<n)__ برقرار باشد، نگاه برای __n__ نیز درست است. #@^
__~~red:با یک مثال روش اثبات را بررسی می کنیم:~~__
دنباله {TEX()} {1,3,4,7,11,18,29,47,...} {TEX} به ((دنباله لوکا)) معروف است که در بین جملات آن رابطه بازگشتی زیر بررار است:
::{TEX()} {L_1=1 ,L_2=3, \forall n\ge 3:L_n=L_{n-1}+L_{n-2}} {TEX}::
با استفاده از اصل استقرای قوی ریاضی نشان می دهیم که برای هر عدد طبیعی n را بطه زیر برقرار است:
::{TEX()} {L_n\le \left (\frac{7}{4} \right)^n} {TEX}::
~~green:پاسخ:~~ اگر
::{TEX()} {S=\{n\in N:L_n\le \left (\frac{7}{4} \right)^n\}} {TEX}::
آنگاه 1و2 عضوی از S می باشند زیرا نامساویهای:
::{TEX()} {L_1=1<\frac{7}{4} ,L_2=3<\left (\frac{7}{4} \right)^2} {TEX}::
درست می باشند.(مرحله مبنا)
حال فرض میکنیم (فرض استقرا) {TEX()} {n\ge 3} {TEX} و به ازای ر عدد طبیعی k ه k، k<n ر مجموعه S قرار دارد. بنابراین:
::{TEX()} {L_{n-1}<\left (\frac{7}{4} \right)^{n-1} ,L_{n-2}<\left (\frac{7}{4} \right)^{n-2}} {TEX}::
لذا چون {TEX()} {L_n=L_{n-1}+L_{n-2}} {TEX} پس:
::{TEX()} {L_n<\left (\frac{7}{4} \right)^{n-1}\,+\left (\frac{7}{4} \right)^{n-2}} {TEX}::
::{TEX()} {\Rightarrow \L_n<\left (\frac{7}{4} \right)^{n-2}\ (\frac{7}{4} +1)} {TEX}::
و از طرفی یگر:
::{TEX()} {\left (\frac{7}{4} \right)^{n-2}\ (\frac{7}{4}+1)<\left (\frac{7}{4} \right)^{n}} {TEX}::
و لــذا:
::{TEX()} {L_n<\left (\frac{7}{4} \right)^n} {TEX}::
یعنی n نیز در مجموعه S قرار دارد، پس مجموعه S همان مجموعه اعداد طبیعی است. و لذا برای هر عدد طبیعی n حکم برقرار است.
---
*~~purple:لازم به توضیح است که از این اصل هم می توان برای اثبات برخی قضایای هندسه استفاده کرد و در ضمن می توان احکامی طبیعی که از یک هم آغاز نمی شوند را به این وسیله اثبات نمود.~~
---
~~red:__مثال:__~~ نشان دهید مجموع زوایای هر n ضلعی محدب برابر است با: {TEX()} {(2n-4)\times 90^\circ} {TEX}
~~green:پاسخ:~~ می دانیم در این سوال n>2 زیرا n ضلعی حداقل از سه ضلع بوجود می آید.
به این ترتیب در مرحله مبنا حکم را برای n=3 بررسی می کنیم:
::{TEX()} {(2\times\,3-4)\times\,90^\circ\,=2\times\,90^\circ\,=180^\circ} {TEX}::
که همان گونه که می دانیم در هندسه نشان داده شده است که مجموع زوایای داخلی هر سه ضلعی محدب(مثلث) برابر {TEX()} {180^\circ} {TEX} می باشد.
اکنون فرض می کنیم (فرض استقرا) که مجموع زاویه های داخلی هر k ضلعی محدب که k<n برابر:
{TEX()} {(2k-4)\times\,90^\circ} {TEX} باشد.
اکنون نشان می دهیم (حکم استقرا) که مجموع زاویه های داخلی هر n ضلعی محدب نیز برابر:
{TEX()} {(2n-4)\times\,90^\circ} {TEX} است.
برای این منظور n ضلعی {TEX()} {A_1A_2A_3...A_n} {TEX} را در نظر می گیریم. قطر {TEX()} {A_1A_k} {TEX} را رسم می کنیم تا n ضلعی به یک k ضلعی: {TEX()} {A_1A_2A_3...A_k} {TEX} و یک (n-k+2) ضلعی {TEX()} {A_1A_kA_{k+1}...A_n} {TEX} تقسیم شود. مطابق فرض استقرا، مجموع زاویه های داخلی k ضلعی و (n-k+2) ضلعی به ترتیب برابر است با:
::{TEX()} {(2k-4)\times\,90^\circ} {TEX} @#14:و#@ {TEX()} {(2n-2k)\times\,90^\circ} {TEX}::
بنابراین مجموع زاویه های داخلی n ضلعی {TEX()} {A_1A_2A_3...A_n} {TEX} برابر است با:
::{TEX()} {(2k-4)\times\,90^\circ\,+(2n-2k)\times\,90^\circ\,=(2n-4)\times\,90^\circ} {TEX}::
و لذا حکم برقرار است.
---
__~~orange:@#14:مزیت و محدودیت اتدلال به کمک استقرای ریاضی:#@~~__
^@#12:استدلال به کمک استقرای ریاضی یک روش مستقیم برای اثبات و حل مسایل ریاضی محسوب می شود. این روش هم امتیازاتی دارد و هم محدودیت هایی. از مزایای استقرای ریاضی، مرحله ای بودن این روش است. یعنی عموما بدون نیاز به ابتکارهای زاید، مفید است و لذا شخص نتها لازوم دارد که برای استدلال خود، از مراحل مشخصی پیروی کند و برای این کار به بینش خاص نیاز نیست. مزیت دیگر این روش این است که استقرای ریاضی در حل مسایل خاصی که در آنها سایر روشهای عملی نیستند و یا بسیار مشکل اند، مفید است.
اما محدودیت استقرای ریاضی در این است که فقط برای مسائلی به کار می رود که با اعداد طبیعی سروکار دارند. لذا این روش اساسا یک روش تحقیق است، و تنها در اثبات نتایجی که درستی آنها را معلوم کرده یا حدس زده ایم، به کار می رود.#@^
--- |
