مقدمه
در بسیاری از مسائل ریاضی باید نشان دهیم یک گزاره نه فقط برای چند عدد مشخص، بلکه برای تمام اعضای یک مجموعه نامتناهی از اعداد طبیعی درست است. برای چنین مسائلی، استقرای ریاضی یکی از مهمترین ابزارهای اثبات محسوب میشود.
در استقرای معمولی، برای اثبات درستی گزاره \(P(n)\) برای همه مقادیر موردنظر، معمولاً نشان میدهیم که درستی \(P(k)\) باعث درستی \(P(k+1)\) میشود. اما در بعضی مسائل، دانستن تنها \(P(k)\) کافی نیست. ممکن است برای اثبات \(P(k+1)\) به \(P(k-1)\)، \(P(k-2)\)، یا حتی چندین حالت پیشین نیاز داشته باشیم.
در چنین شرایطی استقرای قوی ابزار طبیعیتری است. در این روش، در گام استقرا فرض میکنیم همه گزارههای پیشین تا مرحله موردنظر درستاند و سپس از این فرض برای اثبات حالت بعدی استفاده میکنیم.
منابع دانشگاهی و کتابهای آموزش اثبات نیز استقرای قوی را با نامهایی مانند Strong Induction، Complete Induction و Course-of-Values Induction معرفی میکنند. این روش در ریاضیات گسسته، نظریه اعداد، الگوریتمها و علوم کامپیوتر کاربرد گستردهای دارد.
پیشنیازهای استقرای قوی
برای درک استقرای قوی، آشنایی با چند مفهوم ساده کافی است.
گزاره \(P(n)\)
فرض کنید برای هر عدد طبیعی \(n\)، گزارهای مانند \(P(n)\) داشته باشیم. هدف ما میتواند اثبات این باشد که \(P(n)\) برای تمام \(n\)های موجود در یک بازه یا برای همه اعداد طبیعی بزرگتر یا مساوی یک مقدار مشخص درست است.
برای مثال، اگر بخواهیم ثابت کنیم مجموع \(n\) عدد طبیعی اول برابر است با
$$
1+2+\cdots+n=\frac{n(n+1)}{2},
$$
میتوان گزاره \(P(n)\) را بهصورت «رابطه بالا برای \(n\) درست است» تعریف کرد.
گام پایه
در روش استقرا باید یک یا چند حالت ابتدایی را مستقیماً ثابت کنیم. اگر اثبات از \(n=1\) شروع شود، معمولاً \(P(1)\) پایه استقرا خواهد بود؛ اما نقطه شروع الزاماً یک نیست و میتواند هر عدد صحیح مشخصی مانند \(0\)، \(2\) یا \(5\) باشد.
گام استقرا
در گام استقرا باید نشان دهیم اگر فرضهای لازم درباره حالتهای قبلی برقرار باشند، گزاره برای حالت بعدی نیز برقرار خواهد بود.
تعریف دقیق استقرای قوی
فرض کنید \(P(n)\) گزارهای درباره اعداد صحیح \(n\) باشد و بخواهیم درستی آن را برای همه \(n\geq b\) ثابت کنیم.
اصل استقرای قوی میگوید اگر:
- \(P(b)\) درست باشد؛
- برای هر \(k\geq b\)، از درستی همه گزارههای \(P(b),P(b+1),\ldots,P(k)\) بتوان درستی \(P(k+1)\) را نتیجه گرفت؛
آنگاه \(P(n)\) برای همه اعداد صحیح \(n\geq b\) درست است.
صورت نمادین این اصل چنین است:
$$
P(b)\land
\left[
\forall k\geq b,\;
\left(
\bigwedge_{j=b}^{k}P(j)
\right)\Rightarrow P(k+1)
\right]
\Rightarrow
\forall n\geq b,\;P(n).
$$
در بیان رایجتر، میتوان گام استقرا را چنین نوشت:
$$
\left(P(b)\land P(b+1)\land\cdots\land P(k)\right)
\Rightarrow P(k+1).
$$
نکته مهم این است که در فرض استقرایی، اجازه داریم همه حالتهای پیشین را فرض کنیم؛ نه فقط حالت \(k\).
ایده شهودی استقرای قوی
استقرای قوی را میتوان با یک زنجیره ساده تصور کرد. فرض کنید برای رسیدن به مرحله بعدی، ممکن است از هر یک از مراحل قبلی کمک بگیریم.
اگر \(P(1)\) را ثابت کنیم و بتوانیم نشان دهیم:
$$
P(1)\Rightarrow P(2),
$$
آنگاه \(P(2)\) نیز درست است. سپس اگر بتوانیم از درستی همه حالتهای قبلی برای اثبات حالت بعدی استفاده کنیم، زنجیره به همین شکل ادامه پیدا میکند:
$$
P(1)\Rightarrow P(2),
$$
$$
P(1)\land P(2)\Rightarrow P(3),
$$
$$
P(1)\land P(2)\land P(3)\Rightarrow P(4),
$$
و به همین ترتیب، همه حالتها اثبات میشوند.
تفاوت اصلی با استقرای معمولی در این است که در مرحله اثبات \(P(k+1)\)، خود را فقط به \(P(k)\) محدود نمیکنیم.
مراحل انجام یک اثبات با استقرای قوی
مرحله اول: تعریف گزاره
ابتدا باید دقیقاً مشخص کنیم چه گزارهای را میخواهیم برای همه مقادیر \(n\) ثابت کنیم. آن را با \(P(n)\) نمایش میدهیم.
مرحله دوم: تعیین نقطه شروع
مشخص کنید اثبات از چه عددی آغاز میشود. اگر گزاره برای همه \(n\geq b\) مطرح شده است، معمولاً ابتدا \(P(b)\) را بررسی میکنیم.
مرحله سوم: اثبات پایه
در این مرحله، بدون استفاده از فرض استقرا نشان میدهیم که \(P(b)\) درست است.
مرحله چهارم: فرض استقرایی قوی
یک عدد صحیح دلخواه \(k\geq b\) در نظر بگیرید و فرض کنید تمام حالتهای پیشین درستاند:
$$
P(b),P(b+1),\ldots,P(k).
$$
این مجموعه فرضها همان چیزی است که استقرای قوی را از شکل معمول استقرا متمایز میکند.
مرحله پنجم: اثبات حالت بعدی
اکنون باید با استفاده از فرضهای بالا ثابت کنیم:
$$
P(k+1).
$$
اگر در اثبات خود به یکی از حالتهای قبلی نیاز داشتیم، میتوانیم از فرض استقرایی مربوط به همان حالت استفاده کنیم؛ مشروط بر اینکه آن حالت واقعاً کوچکتر یا مساوی \(k\) باشد.
مرحله ششم: نتیجهگیری
پس از اثبات پایه و گام استقرا، نتیجه میگیریم که گزاره برای تمام مقادیر موردنظر درست است.
تفاوت استقرای قوی و استقرای معمولی
در استقرای معمولی، فرض استقرایی معمولاً فقط شامل \(P(k)\) است و هدف اثبات \(P(k+1)\) است:
$$
P(k)\Rightarrow P(k+1).
$$
در استقرای قوی، فرض استقرایی شامل همه حالتهای پیشین است:
$$
P(b)\land P(b+1)\land\cdots\land P(k)
\Rightarrow P(k+1).
$$
| ویژگی |
استقرای معمولی |
استقرای قوی |
| پایه |
یک یا چند حالت اولیه |
یک یا چند حالت اولیه، در صورت نیاز |
| فرض استقرایی |
معمولاً فقط \(P(k)\) |
همه حالتها از نقطه شروع تا \(P(k)\) |
| هدف گام استقرا |
\(P(k+1)\) |
\(P(k+1)\) |
| کاربرد معمول |
وقتی حالت بعدی مستقیماً از حالت قبلی به دست میآید |
وقتی حالت بعدی به یک یا چند حالت قبلی وابسته است |
استقرای قوی از نظر منطقی یک اصل متفاوت و «قویتر» به معنای اثبات نتیجهای بیشتر نیست؛ تفاوت در شکل فرض استقرایی است. استقرای معمولی و استقرای قوی از نظر قدرت اثباتی معادلاند، اما ممکن است یکی برای یک مسئله بسیار طبیعیتر و سادهتر از دیگری باشد.
قضیه: اصل استقرای قوی
قضیه. اگر \(P(n)\) برای \(n\geq b\) تعریف شده باشد و دو شرط زیر برقرار باشند:
- \(P(b)\) درست باشد.
- برای هر \(k\geq b\)، اگر \(P(j)\) برای همه \(j\)های بین \(b\) و \(k\) درست باشد، آنگاه \(P(k+1)\) نیز درست باشد.
در این صورت:
$$
\forall n\geq b,\;P(n).
$$
ایده اثبات
ایده اثبات را میتوان با یک استقرای معمولی روی گزارهای جدید توضیح داد. گزاره جدید را چنین تعریف کنید:
$$
Q(k): P(b)\land P(b+1)\land\cdots\land P(k).
$$
طبق فرض پایه، \(Q(b)\) درست است، زیرا \(P(b)\) درست است.
اکنون اگر \(Q(k)\) درست باشد، تمام گزارههای \(P(b)\) تا \(P(k)\) درستاند. بر اساس فرض گام استقرای قوی، این موضوع باعث میشود \(P(k+1)\) نیز درست باشد. بنابراین \(Q(k+1)\) نیز برقرار است.
پس با استقرای معمولی، \(Q(k)\) برای همه \(k\geq b\) درست است و در نتیجه \(P(n)\) نیز برای همه \(n\geq b\) برقرار خواهد بود.
فرمول و الگوی استاندارد نوشتن اثبات
یک الگوی مناسب برای نوشتن اثبات با استقرای قوی به شکل زیر است:
$$
\boxed{
\begin{aligned}
&\text{پایه: } P(b)\text{ را ثابت میکنیم.}\\[4pt]
&\text{فرض استقرایی: فرض میکنیم }P(j)\text{ برای همه }b\leq j\leq k\text{ درست است.}\\[4pt]
&\text{گام استقرا: با استفاده از این فرضها، }P(k+1)\text{ را ثابت میکنیم.}\\[4pt]
&\text{نتیجه: }P(n)\text{ برای همه }n\geq b\text{ درست است.}
\end{aligned}
}
$$
در یک اثبات رسمی، عبارت «فرض میکنیم همه حالتهای قبلی درستاند» کافی نیست؛ باید مشخص شود این فرض دقیقاً برای چه مقادیری از \(j\) برقرار است.
مثال اول: تجزیه هر عدد صحیح بزرگتر از یک به عوامل اول
یکی از نمونههای کلاسیک و بسیار مناسب برای استقرای قوی این گزاره است:
هر عدد صحیح \(n>1\) را میتوان بهصورت حاصلضرب یک یا چند عدد اول نوشت.
این گزاره را برای \(n\geq2\) ثابت میکنیم.
گام پایه
برای \(n=2\)، عدد \(2\) خودش اول است؛ بنابراین میتوان آن را حاصلضرب یک عدد اول در نظر گرفت. پس \(P(2)\) درست است.
فرض استقرایی
فرض کنید برای یک \(k\geq2\)، تمام اعداد صحیح از \(2\) تا \(k\) را بتوان به حاصلضرب اعداد اول تجزیه کرد:
$$
P(2),P(3),\ldots,P(k).
$$
باید نشان دهیم \(k+1\) نیز چنین تجزیهای دارد.
گام استقرا
دو حالت داریم.
حالت اول: \(k+1\) اول است
در این صورت خود \(k+1\) یک عدد اول است و بنابراین بهطور مستقیم حاصلضرب یک عدد اول است.
حالت دوم: \(k+1\) مرکب است
چون \(k+1\) مرکب است، میتوان آن را به صورت
$$
k+1=ab
$$
نوشت که در آن:
$$
1<><>
بنابراین \(a\) و \(b\) هر دو بین \(2\) و \(k\) قرار دارند. طبق فرض استقرایی، هر دو را میتوان به حاصلضرب اعداد اول تجزیه کرد:
$$
a=p_1p_2\cdots p_r
$$
و
$$
b=q_1q_2\cdots q_s.
$$
در نتیجه:
$$
k+1=ab
=(p_1p_2\cdots p_r)(q_1q_2\cdots q_s),
$$
که خود یک حاصلضرب از اعداد اول است.
پس در هر دو حالت، \(P(k+1)\) درست است. بنابراین طبق اصل استقرای قوی، هر عدد صحیح بزرگتر از \(1\) حاصلضرب یک یا چند عدد اول است.
این مثال دقیقاً نشان میدهد چرا استقرای قوی مفید است. برای تجزیه \(k+1\)، ممکن است به گزاره مربوط به \(a\) یا \(b\) نیاز داشته باشیم و هیچ تضمینی وجود ندارد که یکی از آنها برابر \(k\) باشد.
مثال دوم: حل رابطه بازگشتی با وابستگی به چند حالت قبلی
فرض کنید دنبالهای به صورت زیر تعریف شده باشد:
$$
a_1=1,\qquad a_2=2,
$$
و برای \(n\geq3\):
$$
a_n=a_{n-1}+a_{n-2}.
$$
میخواهیم نشان دهیم:
$$
a_n<2^n
$$
برای همه \(n\geq1\).
پایههای استقرا
برای \(n=1\):
$$
a_1=1<2=2^1.
$$
برای \(n=2\):
$$
a_2=2<4=2^2.
$$
پس دو حالت ابتدایی درستاند.
فرض استقرایی قوی
فرض کنید برای یک \(k\geq2\)، برای همه \(j\)های بین \(1\) و \(k\) داشته باشیم:
$$
a_j<2^j.
$$
در گام بعد باید ثابت کنیم:
$$
a_{k+1}<2^{k+1}.
$$
از رابطه بازگشتی داریم:
$$
a_{k+1}=a_k+a_{k-1}.
$$
طبق فرض استقرایی:
$$
a_k<2^k
$$
و
$$
a_{k-1}<2^{k-1}.
$$
بنابراین:
$$
a_{k+1}
<2^k+2^{k-1}
<2^k+2^k
=2^{k+1}.
$$
پس \(P(k+1)\) درست است و در نتیجه:
$$
\boxed{a_n<2^n\quad\text{برای همه }n\geq1.}
$$
در این مثال، رابطه بازگشتی مستقیماً به دو جمله قبلی وابسته است. بنابراین استقرای قوی ساختار مناسبی برای اثبات کران موردنظر فراهم میکند؛ هرچند بسته به صورت دقیق گزاره، استقرای معمولی با فرضهای کمکی نیز میتواند قابل استفاده باشد.
مثال سوم: پرداخت مبلغ با سکههای مشخص
فرض کنید سکههایی به ارزش \(3\) و \(5\) واحد در اختیار داریم. میخواهیم نشان دهیم هر عدد صحیح \(n\geq8\) را میتوان به صورت مجموع چند سکه ۳ و ۵ واحدی پرداخت کرد.
گزاره \(P(n)\) را اینگونه تعریف میکنیم:
«عدد \(n\) را میتوان به صورت \(3a+5b\)، با \(a,b\) اعداد صحیح نامنفی، نوشت.»
پایهها
سه عدد نخست را بررسی میکنیم:
$$
8=3+5,
$$
$$
9=3+3+3,
$$
$$
10=5+5.
$$
بنابراین \(P(8)\)، \(P(9)\) و \(P(10)\) درستاند.
فرض استقرایی
فرض کنید برای همه اعداد صحیح \(j\) که
$$
8\leq j\leq k
$$
داریم \(P(j)\).
میخواهیم \(P(k+1)\) را ثابت کنیم.
برای \(k\geq10\)، عدد \(k-2\) دستکم برابر ۸ است و از \(k\) کوچکتر است. بنابراین طبق فرض استقرایی، \(k-2\) را میتوان با سکههای ۳ و ۵ ساخت. پس با افزودن یک سکه ۳ واحدی داریم:
$$
k+1=(k-2)+3.
$$
بنابراین \(k+1\) نیز قابل پرداخت است.
پس همه اعداد صحیح \(n\geq8\) را میتوان با سکههای ۳ و ۵ واحدی ساخت.
این مثال نشان میدهد که در استقرای قوی لازم نیست حالت \(k+1\) از \(P(k)\) به دست بیاید. در اینجا از حالت \(P(k-2)\) استفاده کردیم.
چه زمانی استقرای قوی انتخاب مناسبی است؟
استقرای قوی معمولاً زمانی انتخاب مناسبی است که ساختار مسئله نشان دهد یک حالت جدید از یک یا چند حالت کوچکتر ساخته میشود، بدون اینکه الزاماً فقط به حالت بلافاصله قبلی وابسته باشد.
نمونههای رایج عبارتاند از:
- تجزیه اعداد به عوامل کوچکتر یا عوامل اول؛
- رابطههای بازگشتی با چند جمله قبلی؛
- مسائلی که یک شیء با شکستن آن به چند شیء کوچکتر بررسی میشود؛
- اثبات برخی خواص الگوریتمهای بازگشتی؛
- مسائل نظریه اعداد و بخشپذیری؛
- مسائل مربوط به ساختارهای گسسته.
در درسهای ریاضیات گسسته و علوم کامپیوتر، استقرای قوی بهطور خاص در اثباتهایی که مسئله به زیرمسئلههای کوچکتر تجزیه میشود، اهمیت دارد.
آیا همیشه باید از استقرای قوی استفاده کرد؟
خیر. استقرای قوی یک ابزار است، نه یک الزام.
اگر برای اثبات \(P(k+1)\) فقط دانستن \(P(k)\) کافی باشد، استقرای معمولی اغلب سادهتر و خواناتر است. در چنین شرایطی استفاده از استقرای قوی ممکن است فرضهای اضافی ایجاد کند که هیچ نقشی در اثبات ندارند.
از طرف دیگر، اگر برای رسیدن به \(P(k+1)\) به \(P(k-2)\)، \(P(k-5)\) یا مجموعهای از حالتهای قبلی نیاز داریم، استقرای قوی معمولاً نوشتن اثبات را طبیعیتر میکند.
بنابراین معیار اصلی این نیست که کدام روش «قویتر» است؛ بلکه باید دید ساختار وابستگی مسئله چگونه است.
اشتباهات رایج در استقرای قوی
۱. اشتباه گرفتن استقرای قوی با استقرای معمولی
در استقرای قوی، فرض استقرایی فقط \(P(k)\) نیست. باید مشخص شود که همه حالتهای لازم تا \(k\) درست فرض شدهاند:
$$
P(b),P(b+1),\ldots,P(k).
$$
۲. استفاده از \(P(k+1)\) در فرض استقرایی
در گام استقرا نباید \(P(k+1)\) را از قبل فرض کنیم؛ زیرا همین گزاره هدف اثبات است. این کار به استدلال دوری منجر میشود.
۳. فراموش کردن پایههای لازم
اگر گام استقرا از چند حالت ابتدایی استفاده کند، باید آن حالتها بهدرستی پوشش داده شوند. برای مثال اگر اثبات \(P(k+1)\) برای اولین بار به \(P(k-2)\) نیاز دارد، باید اطمینان حاصل کنیم این حالت در دامنه فرض استقرایی قرار دارد.
۴. مبهم نوشتن محدوده فرض استقرایی
عبارت «فرض میکنیم موارد قبلی درستاند» از نظر آموزشی و گاهی از نظر منطقی کافی نیست. بهتر است دقیقاً بنویسیم:
$$
\text{فرض میکنیم برای هر }j\text{ با }b\leq j\leq k,\quad P(j)\text{ درست است.}
$$
۵. استفاده از حالتهایی خارج از فرض
اگر فرض استقرایی فقط برای \(j\geq b\) برقرار است، نمیتوان بدون بررسی از گزارهای مانند \(P(k-5)\) استفاده کرد؛ باید مطمئن شویم:
$$
k-5\geq b.
$$
این موضوع بهخصوص در نخستین مراحل گام استقرا اهمیت دارد.
نکات مهم برای نوشتن یک اثبات صحیح
- ابتدا گزاره \(P(n)\) را دقیق تعریف کنید.
- نقطه شروع استقرا را مشخص کنید.
- پایه یا پایههای لازم را جداگانه ثابت کنید.
- در فرض استقرایی دامنه شاخصها را دقیق بنویسید.
- در گام استقرا فقط از فرضهایی استفاده کنید که واقعاً در دسترساند.
- بهوضوح مشخص کنید چگونه از حالتهای قبلی به حالت \(k+1\) میرسید.
- در پایان، نتیجه استقرا را صریحاً بیان کنید.
رابطه استقرای قوی با استقرای معمولی
از نظر منطقی، استقرای قوی و استقرای معمولی همارز هستند. یعنی اگر یک گزاره با استقرای قوی اثبات شود، اصل استقرا را میتوان به شکلی معادل برای اثبات آن به کار برد و برعکس.
تفاوت اصلی در شکل استدلال است. در استقرای معمولی، ساختار اصلی چنین است:
$$
P(k)\Rightarrow P(k+1).
$$
اما در استقرای قوی ساختار به شکل زیر است:
$$
\left(\forall j,\;b\leq j\leq k\Rightarrow P(j)\right)
\Rightarrow P(k+1).
$$
در نتیجه، واژه «قوی» نباید به این معنا برداشت شود که استقرای قوی قادر به اثبات قضایایی است که استقرای معمولی اصولاً نمیتواند اثبات کند. منظور از قوی بودن، قویتر بودن فرضی است که در گام استقرا در اختیار نویسنده قرار میگیرد.
کاربردهای استقرای قوی
نظریه اعداد
اثبات نتایجی درباره تجزیه اعداد، بخشپذیری و ساختار اعداد صحیح از کاربردهای مهم استقرای قوی است.
ریاضیات گسسته
در مسائل مربوط به ساختارهای متناهی و فرایندهایی که یک شیء را به اجزای کوچکتر تقسیم میکنند، استقرای قوی بسیار مفید است.
علوم کامپیوتر
الگوریتمهای بازگشتی اغلب مسئلهای با اندازه \(n\) را به مسئلههایی با اندازه کوچکتر تبدیل میکنند. این ساختار با ایده استقرای قوی ارتباط نزدیکی دارد و میتوان برای اثبات درستی برخی الگوریتمهای بازگشتی از آن استفاده کرد.
روابط بازگشتی
وقتی مقدار یک دنباله به چند جمله پیشین وابسته باشد، استقرای قوی میتواند ابزار مناسبی برای اثبات کرانها یا ویژگیهای آن دنباله باشد.
یک چکلیست سریع برای حل مسائل استقرای قوی
- گزاره \(P(n)\) را مشخص کنید.
- نقطه شروع \(b\) را پیدا کنید.
- پایه استقرا را ثابت کنید.
- یک \(k\) دلخواه در محدوده موردنظر انتخاب کنید.
- فرض کنید \(P(j)\) برای همه \(b\leq j\leq k\) درست است.
- بررسی کنید برای اثبات \(P(k+1)\) به کدام حالتهای قبلی نیاز دارید.
- از همان فرضهای مجاز استفاده کنید.
- \(P(k+1)\) را ثابت کنید.
- در پایان، نتیجه را برای همه \(n\geq b\) اعلام کنید.
موضوعات مرتبط
برای مطالعه مرحلهای مباحث مرتبط با اثباتهای ریاضی، این موضوعات را نیز دنبال کنید:
جمعبندی
استقرای قوی روشی برای اثبات گزارههایی است که برای همه اعضای یک دنباله از اعداد یا ساختارهای مرتبشده مطرح میشوند. تفاوت اصلی آن با استقرای معمولی این است که در گام استقرا، بهجای فرض تنها یک حالت قبلی، درستی همه حالتهای پیشین تا مرحله \(k\) را فرض میکنیم.
صورت اصلی این روش چنین است: ابتدا یک حالت پایه را ثابت میکنیم؛ سپس نشان میدهیم اگر همه حالتهای پیشین درست باشند، حالت بعدی نیز درست است. در این صورت گزاره برای تمام مقادیر موردنظر برقرار خواهد بود.
مهمترین نشانه برای انتخاب استقرای قوی این است که حالت جدید از یک یا چند حالت کوچکتر ساخته شود و الزاماً فقط به حالت بلافاصله قبل وابسته نباشد. تجزیه اعداد به عوامل اول، روابط بازگشتی و بسیاری از مسائل ریاضیات گسسته نمونههای طبیعی این روش هستند.
منابع
تاریخ بررسی منابع: ۲۲ مرداد ۱۴۰۵