اصل استقراء ریاضی
اصل استقرای ریاضی:
این اصل بیان میکند اگر S زیرمجموعه ای ناتهی از اعداد طبیعی باشد به طوری که:
۱) عدد یک عضو این مجموعه باشد.
۲) هرگاه عدد طبیعی n در مجموعه S باشد آنگاه n+1 نیز عضو این مجموعه باشد.
میتوان تنیجه گرفت هر عدد طبیعی عضو S است و به عبارت دیگر S همان مجموعه اعداد طبیعی است.

لازم به توضیح است این اصل با پذیرش اصل خوش ترتیبی قابل اثبات است.
برهان:

برای اثبات از برهان خلف کمک می گیریم. به برهان خلف فرض می کنیم با مفروضات فوق مجموعه S برابر مجموعه اعداد طبیعی نباشد. پس مجموعه ای چون T وجود دارد که S=N-T. حال داریم: مجموعه T زیر مجموعه اعداد طبیعی است و ناتهی است(چرا؟) پس بنا بر اصل خوشترتیبی T دارا عضو مینیمم است چون واضح است که و چون پس داریم: و چون برابر مینیمم مجموعه T است پس و لذا از شرط دوم مجموعه S داریم:
که این تناقض است چون پس فرض خلف باطل و حکم(اصل اسقرا) برقرار است.

• به این ترتیب برای اثبات برخی از مسائل و احکام ریاضی که درباره اعداد طبیعی می باشند می توان از اصل استقرای ریاضی استفاده کرد که اثبات به این روش، یک روش مستقیم در استدلال ریاضی است.

صورتی دیگر از اصل استقرای ریاضی:(اثبات به کمک اصل استقرای ریاضی(

همان گونه که گفته شد از اصل استقرا برای اثبات احکامی در مورد اعداد طبیعی استفاده می شود. حال روش اثبات را بوسیله این اصل بیان می کنیم:
اگر (P(n حکمی در مورداعداد طبیعی باشد (P(n برای هر عدد طبیعی n درست است اگر و فقط اگر:
۱- حکم (P(1 درست باشد. به عبارت دیگر حکم برای n=1 برقرار باشد. (این مرحله را مرحله مبنای استقرا می گوییم.)
۲- به ازای هر عدد طبیعی k از فرض درستی (P(k (فرض استقرا) بتوان درستی (P(k+1 (حکم استقرا) را نتیجه گرفت.

به عبارت دیگر نشان می دهیم عدد ۱ در دامنه حکم است و چون هر k طبیعی که در دامنه حکم باشد k+1 هم در دامنه است می توان گفت دامنه حکم هر عدد طبیعی است و هر عدد طبیعی در حکم صدق می کند.
• لازم به توضیح است که در اثبات به کمک اصل استقرا هر یک دو شرط فوق باید برقرار باشد تا بتوان درستی حکم را نتیجه گرفت.

مثال: نشان دهید برای هر عدد طبیعی n:

پاسخ: اثبات را با استفاده از اصل استقرای ریاضی انجام می دهیم:
۱- درستی حکم داده شده را برای n=1 بررسی می کنیم: (مرحله مبنایی استقرا)
سمت راست تساوی: ۴
سمت چپ تساوی:
پس برای n=1 طرفین تساوی دادهشده با هم برابر می شوند که نشان می دهد حکم برای n=1 درست است.
۲- فرض می کنیم تساوی داده شده به ازای عدد طبیعی n=k برقرار باشد(فرض استقرا) یعنی:

حال نشان میدهیم حکم برای n=k+1 هم برقرار است(حکم استقرا) یعنی:

برای اثبات حکم استقرا از فرض استقرا کمک می گیریم. برای این کار به طرفین فرض استقرا عبارت را اضافه میکنیم:

حال در سمت راست تساوی فوق داریم:

پس نشان داده شد:
به این ترتیب بر طبق اصل استقرا حکم فوق برای هر n عضو اعداد طبیعی برقرار است.
________________________________________
اصل استقراء تعمیم یافــته:
گاهی ممکن است با احکامی روبه رو شویم که برای n=1 برقرار نمی باشند و باید در بررسی شرط اول (مرحله مبنا) از عددی طبیعی بزرگتر استفاده کنیم به این ترتیب از اصل استقراء تعمیم یافــته استفاده می کنیم.
اصل استقرای تعمیم یافته:
اگر (P(nحکمی در باره اعداد طبیعی n (یا صحیح) باشد در صورتی که:
۱- برای هر عدد طبیعی P(m) ، m>1 درست باشد
۲- به ازای هر عدد طبیعی ، از درستی (P(k درستی (P(k+1 نتیجه شود
آنگاه میتوان گفت حکم (P(n برای هر عدد طبیعی برقرار است.

• به این ترتیب در اثبات مسائل به کمک اصل استقرای تعمیم یافته باید m مناسب را برای بررسی شرط اول بیابیم.
________________________________________
مثال: نشان دهید عدد طبیعی مناسبی مانند m وجود دارد که برای هر عدد طبیعی n بزرگتر یا مساوی m داریـم:

پاسخ: با قرار دادن مقادیر طبیعی برای m متوجه می شویم که m مناسب ۳ است چرا که برای اولین بار حکم برای m=3 درست است. حال نشان میدهیم حکم برای هر عدد طبیعی برقرار است.
۱-
۲- اکنون در این مرحله فرض (فرض استقرا) می کنیم نامساوی فوق برای هر عدد طبیعی درست باشد یعنی:
نشان میدهیم حکم داده شده برای (n=k+1 ،(k>2 درست است، یعنی:
(حکم استقرا)
برای این منظور از فرض استقرا استفاده کرده و به طرفین فرض عدد ۲ را اضافه می کنیم، داریم:

حال با مقایسه نامساوی اخیر و حکم استقرا کافی است نشان دهیم:

برای این کار از اثبات بازگشتی کمک میگیریم:

مشاهده می شود نامساوی برای K>2 همواره درست است و چون تمامی روابط برگشت پذیرند، لذا برقرار بوده و به این ترتیب حکم برای هر عدد طبیعی برقرار است.
________________________________________
• لازم به توضیح است که از اصل استقرای ریاضی میتوان در اثبات برخی قضایای هندسه نیز استفاده نمود.
________________________________________
مثال: نشان دهید در هر n ضلعی محدب تعداد قطرها برابر است با:

پاسخ: می دانیم یک ۳ ضلعی محدب، مثلث دارای هیچ قطری نمی باشد و چهار ضلعی محدب دارای
دو قطر است. به این ترتیب حکم را برای n>3 اثبات می کنیم. مرحله اول (مبنا) را با n=4 آغاز می کنیم:
۱-
حال فرض می کنیم که حکم برای n=k درست باشد، یعنی تعداد قطرهای هر k ضلعی محدب برابر باشد با:

نشان می دهیم که حکم برای n=k+1 هم درست است، یعنی تعداد قطرهای هر k+1 ضلعی محدب برابر است با:

برای اثبات سعی می کنی به گونه ای از فرض استقرا استفاده کنیم. به این صورت که می دانیم که اگر به تعداد ضلعهای یک n ضلعی، یک ضلع اضافه کنیم یا به تعداد رئوس آن یک راس اضافه کنیم به تعداد قطرهای آن n-1 واحد اضافه می شود. لذا:
(k-1)+تعداد قطرهای k ضلعی محدب=تعداد قطرهای k+1 ضلعی محدب

بنابراین رابطه زیر برقرار است:
تعداد قطرهای k+1 ضلعی محدب

و لذا حکم برای هر n>3 برقرار است.
________________________________________
اصل استقرای قوی ریاضی:
صورتی دیگر از اصل استقرای ریاضی به شکل زیر مطرح می شود، که به اصل استقرای قوی ریاضی موسوم است. این اصل با اصل استقرای ریاضی و در نتیجه با اصل خوش ترتیبی معادل است.
اصل استقرای قوی ریاضی:
اگر S زیرمجموعه ای از اعداد طبیعی باشد، به طوری که:
۱- عدد یک عضوی از مجموعه S باشد.
۲- اگر اعداد طبیعی کوچکتر از n در مجموعه S باشند، آنگاه n نیز عضو S باشد
در این صورت هر عدد طبیعی عضوی از S است و به عبارت دیگر S همان مجموعه اعداد طبیعی است.

• لازم به تذکر است در ریاضیات برای اثبات احکام طبیعی بیشتر از اصل استقرای قوی ریاضی استفاده میشود.
________________________________________
روش اثبات احکام بوسیله اصل استقرای قوی ریاضی:
مراحل اثبات به کمک اصل استقرای قوی ریاضی به این صورت است:
۱- درستی حکم را برای n=1 بررسی می کنیم.
۲- نشان می دهیم که اگر حکم داده شده به ازا هر عدد طبیعی k که (k<n) برقرار باشد، نگاه برای n نیز درست است.

با یک مثال روش اثبات را بررسی می کنیم:

دنباله به دنباله لوکا معروف است که در بین جملات آن رابطه بازگشتی زیر برقرار است:

با استفاده از اصل استقرای قوی ریاضی نشان می دهیم که برای هر عدد طبیعی n را بطه زیر برقرار است:

پاسخ: اگر

آنگاه ۱و۲ عضوی از S می باشند زیرا نامساویهای:

درست می باشند.(مرحله مبنا)
حال فرض میکنیم (فرض استقرا) و به ازای هر عدد طبیعی k که k، k<n در مجموعه S قرار دارد. بنابراین:

لذا چون پس:

و از طرفی دیگر:

و لــذا:

یعنی n نیز در مجموعه S قرار دارد، پس مجموعه S همان مجموعه اعداد طبیعی است. و لذا برای هر عدد طبیعی n حکم برقرار است.
________________________________________
• لازم به توضیح است که از این اصل هم می توان برای اثبات برخی قضایای هندسه استفاده کرد و در ضمن می توان احکامی طبیعی که از یک هم آغاز نمی شوند را به این وسیله اثبات نمود.
________________________________________
مثال: نشان دهید مجموع زوایای هر n ضلعی محدب برابر است با:
پاسخ: می دانیم در این سوال n>2 زیرا n ضلعی حداقل از سه ضلع بوجود می آید.
به این ترتیب در مرحله مبنا حکم را برای n=3 بررسی می کنیم:

که همان گونه که می دانیم در هندسه نشان داده شده است که مجموع زوایای داخلی هر سه ضلعی محدب(مثلث) برابر می باشد.
اکنون فرض می کنیم (فرض استقرا) که مجموع زاویه های داخلی هر k ضلعی محدب که k<n برابر:
باشد.
اکنون نشان می دهیم (حکم استقرا) که مجموع زاویه های داخلی هر n ضلعی محدب نیز برابر:
است.
برای این منظور n ضلعی را در نظر می گیریم. قطر را رسم می کنیم تا n ضلعی به یک k ضلعی: و یک (n-k+2) ضلعی تقسیم شود. مطابق فرض استقرا، مجموع زاویه های داخلی k ضلعی و (n-k+2) ضلعی به ترتیب برابر است با:
و

بنابراین مجموع زاویه های داخلی n ضلعی برابر است با:

و لذا حکم برقرار است.
________________________________________
مزیت و محدودیت استدلال به کمک استقرای ریاضی:
استدلال به کمک استقرای ریاضی یک روش مستقیم برای اثبات و حل مسایل ریاضی محسوب می شود. این روش هم امتیازاتی دارد و هم محدودیت هایی. از مزایای استقرای ریاضی، مرحله ای بودن این روش است. یعنی عموما بدون نیاز به ابتکارهای زاید، مفید است و لذا شخص نتها لازوم دارد که برای استدلال خود، از مراحل مشخصی پیروی کند و برای این کار به بینش خاص نیاز نیست. مزیت دیگر این روش این است که استقرای ریاضی در حل مسایل خاصی که در آنها سایر روشهای عملی نیستند و یا بسیار مشکل اند، مفید است.

اما محدودیت استقرای ریاضی در این است که فقط برای مسائلی به کار می رود که با اعداد طبیعی سروکار دارند. لذا این روش اساسا یک روش تحقیق است، و تنها در اثبات نتایجی که درستی آنها را معلوم کرده یا حدس زده ایم، به کار می رود.