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