منو
 کاربر Online
735 کاربر online
تاریخچه ی: اصل استقراء ریاضی

تفاوت با نگارش: 1

Lines: 1-27Lines: 1-149
-((اصل استقراء ریاضی))
طبق این اصل داریم
:<br />اگر S مجموعه ای ناتهی باشد آنگاه با دو شرط زیر با مجموعه اعداد طبیعی(N) برابر خواهد بود:
1)یک عضو این مجموعه باشد
2)به ازای تمام اعداد طبیعی n واقع بر مجموعه S ، n+1 نیز عضو آن مجموعه باشد.
از این
اصل برای ثبات برخی از رمولی های ریاضیا در زمینه اعداد گسسته و طبیعی استفاده می شود.
+__@#16:~~brown:اصل اترای ریاضی:~~#@__
-!اص اترای یاضی ب ه ال قسیم می ش: />!!ال اقرای معمولی یا ی:
مق این اگر P(n)حکمی برای مجموعه ی ا اعداد طبیعی باشد و P رای 1n= درست باشد از تی P(k) ( ستقرا) بتوانیم ه رستی P(k+1) برسیم. د ین وت به این نتیه می رسیم که که حکم P(n) برای م اعدا طبیعی درست است.
!!!سال مربو ه استقرای ی یا مولی: />مل1) ت کنی:
1+3+5+…+(2n-1
)=n^2 />اثبات از طریق استقراء:
P(1)=1 correct
1+3+5+…+(2k-1)=k^2 فض استقرا
1+3+5+….+(2k+1)=(k+1)^2 حک
استرا:
+^@#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:را:#@~~__
-1+3+5++(2k-1)=k^2 --à 1+3+5++(2k-1)+(2k+1)=k^2 +2k+1 (طبق اتحاد) -à
1+3+5++(2k-1)+(2k+1)= (k+1)^2
!!اصل استقرای قوی:
!!اصل اسقرای تعمیم یافته:
+ @#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+...+(5
k-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+...+(5
k-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:استدلال به کمک استقرای ریاضی یک روش مستقیم برای اثبات و حل مسایل ریاضی محسوب می شود. این روش هم امتیازاتی دارد و هم محدودیت هایی. از مزایای استقرای ریاضی، مرحله ای بودن این روش است. یعنی عموما بدون نیاز به ابتکارهای زاید، مفید است و لذا شخص نتها لازوم دارد که برای استدلال خود، از مراحل مشخصی پیروی کند و برای این کار به بینش خاص نیاز نیست. مزیت دیگر این روش این است که استقرای ریاضی در حل مسایل خاصی که در آنها سایر روشهای عملی نیستند و یا بسیار مشکل اند، مفید است.
اما محدودیت استقرای ریاضی در این است که فقط برای مسائلی به کار می رود که با اعداد طبیعی سروکار دارند. لذا این روش اساسا یک روش تحقیق است، و تنها در اثبات نتایجی که درستی آنها را معلوم کرده یا حدس زده ایم، به کار می رود.#@^
---
 !پیوست مربوطه: !پیوست مربوطه:
 *((اصل خوش ترتیبی)) *((اصل خوش ترتیبی))
 *((تئوری اعداد)) *((تئوری اعداد))
 *((ریاضیات گسسته)) *((ریاضیات گسسته))

تاریخ شماره نسخه کاربر توضیح اقدام
 چهارشنبه 24 خرداد 1385 [05:39 ]   5   مرادی فر      جاری 
 شنبه 30 اردیبهشت 1385 [03:35 ]   4   مرادی فر      v  c  d  s 
 شنبه 23 اردیبهشت 1385 [03:43 ]   3   مرادی فر      v  c  d  s 
 دوشنبه 08 فروردین 1384 [20:49 ]   2   احمد شکیب      v  c  d  s 
 دوشنبه 08 فروردین 1384 [20:35 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..