پرش به محتوا
ورود | ثبت‌نام
سخنان قصار
  • سعی كن درزندگی برنامه مشخصی داشته باشی و هدفت رابدانی. اما اگراتفاق عجیب و غیر منتظره ای هم پیش آمد، ازخودت انعطاف نشان بده.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • وقتی خانمی را به خانه اش می رسانی تا وقتی مطمئن نشده ای كه به سلامت وارد خانه اش شده آنجا را ترك نكن.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • بدترین دوست،‌ کسی است که برای او به رنج و زحمت افتی.امام علی (ع)
  • نردبان، سیم رابط و شلنگ را همیشه بلندتر از مقدار مورد نیاز بخر.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • سعی كن بهترین معلم فرزندانت باشی.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • در دبیرستان طوری رفتار كن كه روز جشن فارغ التحصیلی اجرای برنامه ها را به محول كنند.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • به مردمی كه شغل دشواری دارند بیشتر احترام بگذار.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • یادت باشد هرچه بیشتر بدانی كمتر خواهی ترسید.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • جاهلان شما پر تلاش، و آگاهان شما تن پرور و كوتاهی ورزند !امام علی (ع)
  • به خاطر داشته باش چیزی كه مهم است ارزش كالاست نه قیمت روی آن.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • سعی كن در محیط مدرسه كاملا آرام باشی.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • وقتی به دیدن دوست بیمار خود می روی به یاد داشته باش كه امید دادن وتقویت افكار مثبت برای او قویترین داروست.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • برای هر كسی در مال او دو شریك است: وارث، و حوادث.امام علی (ع)
  • برترین بی نیازی و دارایی، ناامیدی است از آنچه در دست مردم است.امام علی (ع)
  • سخت ترین گناهان، گناهی است كه گناهكار آن را سبك شماردامام علی (ع)
  • نابود شد ، كسی كه ارزش خود را ندانستامام علی (ع)
  • دائما درانتظار رسیدن الهامات نوید بخش نباش ، تو تلاش كن ، آنها خود به سراغت خواهند آمد.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • پیش از ازدواج حداقل شش ماه با همسرت نامزد باش .اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • از حرام دنیا چشم پوش، تا خدا زشتی های آن ر ا به تو نمایاند، و غافل مباش كه لحظه ای از تو غفلت نشود.امام علی (ع)
  • وقتی چیزی را می بینی كه خیلی دلت می خواهد مال تو باشد به خاطر مقدار كمی پول آن را از دست نده.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • بسا سخن كه از حملة مسلحانه كارگر تر استامام علی (ع)
  • سخت ترین گناه آنكه گناهكاران را كوچك بشماردامام علی (ع)
  • به یك دانش آموز نیازمند كمك كن تا در اردوهای تابستانی شركت كند.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • وقتی فردی شریف پستی سیاسی برعهده می گیرد، سعی كن تا جایی كه در توان داری ، چه مالی و چه معنوی ، از و حمایت كنی .اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • از نافرمانی خدا در خلوت ها بپرهیزید، زیرا همان كه گواه است، داوری كند.امام علی (ع)
  • در تربیت خویش تو را بس كه از آنچه بر دیگران نمی پسندی دوری كنی.امام علی (ع)
  • هرسال یك اثر هنری بخر، حتی اگر كاری مانند نقاشی رنگ و روغن یك دانش آموز دبیرستانی باشد.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • هرچه را كه می شنوی باور نكن.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • مردم فرزندان دنیا هستند و هیچ كس را بر دوستی مادرش نمی توان سرزنش كرد.امام علی (ع)
  • هر گاه مستحبات به واجبات زیان رساند آن را ترك كنید.امام علی (ع)
  • سعی كن هر كاری را قبل از موعد مقرر به انجام برسانی.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • اگر خواستی كسی را خوب بشناسی، دوستانش را ببین، به این ترتیب چیزهای زیادی درباره اش خواهی فهمید.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • سعی كن ازآن افرادی نباشی كه می گویند: ((آماده ، هدف ، آتش ))اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • چند تردستی كوچك یاد بگیر.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • ای فرزند آدم ! اندوه روز نیامده را بر امروزت میفزا، زیرا اگر روز نرسیده، از عمر تو باشد خدا روزی تو را خواهد رساند.امام علی (ع)
  • خوشبختی به آسانی به دست نمی آید ، برای به دست آوردن آن باید سخت تلاش كنی.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • كاری را كه باید انجام دهی با شادی و نشاط انجام بده .اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • از دیگران انتظار نداشته باش كه بهترین هدیه ها را به بهترین شكل كادوپیچی كرده و به تو بدهند.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • ماهی یكبار غذاهای مفصل و كامل بخور، هرباردر یك رستوران.اچ جکسون براون (کتاب نکته‌های کوچک زندگی)
  • دو گرسنه هرگز سیر نشوند: جویندة علم و جویندة مالامام علی (ع)
مطالب علمی
۷ دقیقه مطالعه دسته‌ها: ریاضیمبانی ریاضیات

استقرای قوی چیست؟ تعریف، اصل استقرای قوی، روش اثبات و مثال‌های حل‌شده

مقدمه

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

در استقرای معمولی، برای اثبات درستی گزاره \(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\) ثابت کنیم.

اصل استقرای قوی می‌گوید اگر:

  1. \(P(b)\) درست باشد؛
  2. برای هر \(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\) تعریف شده باشد و دو شرط زیر برقرار باشند:

  1. \(P(b)\) درست باشد.
  2. برای هر \(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
۶۷ بازدید کد مطلب 7597
کلمات کلیدی:

مطالب مرتبط

نظرات (۰)

هنوز نظری ثبت نشده است. اولین نفر باشید!

نوشتن نظر

استقرای قوی چیست؟ تعریف، اصل استقرای قوی، روش اثبات و مثال‌های حل‌شده — https://www.rayeshmand.ir/article/strong-induction

دسته بندی مقالات