استقرا تعمیم یافته

گاهی ممکن است با احکامی روبه رو شویم که برای n=۱ برقرار نمی‌باشند و باید در بررسی شرط اول (مرحله مبنا) از عددی طبیعی بزرگتر استفاده کنیم به این ترتیب از اصل استقرا تعمیم یافته استفاده می‌کنیم. استقرای تعمیمی از جز به کل می‌شود. یعنی با بررسی چند مورد از یک جامعه آماری آنرا به کل جامعه سرایت می‌دهیم.

مراحل استقرا تعمیم یافته

اگر (P(n حکمی دربارهٔ اعداد طبیعی n (یا اعداد صحیح) باشد در صورتی که:

1. برای هر عدد طبیعی P(m) , m>1 درست باشد.
2. به ازای هر عدد طبیعی، از درستی (P(k درستی (P(k+1نتیجه شود.

آنگاه می‌توان گفت حکم (P(n برای هر عدد طبیعی n=>m برقرار است.

به این ترتیب در اثبات مسائل به کمک اصل استقرای تعمیم یافته باید m مناسب را برای بررسی شرط اول بیابیم.

مثال

نشان دهید عدد طبیعی مناسبی مانند m وجود دارد که برای هر عدد طبیعی n بزرگتر یا مساوی m داریم:

$2(n)+1<2^{n}$

پاسخ:با قرار دادن مقادیر طبیعی برای m متوجه می‌شویم که m مناسب ۳ است چرا که برای اولین بار حکم برای m=۳ درست است. حال نشان می‌دهیم حکم برای هر عدد طبیعی درست است

1. اول به ازای n=۳ درست است:

$2(3)+1<2^{3}$

1. اکنون در این مرحله فرض (فرض استقرا) می‌کنیم نامساوی فوق برای هر عدد طبیعی درست باشد یعنی:

$k=>3:2k+1<2^{k}$

نشان می‌دهیم حکم داده شده برای (n=k+1 ،(k>2 درست است، یعنی:

$n=k+1,(k=>3):2k+3<2^{k+1}$

برای این منظور از فرض استقرا استفاده کرده و به طرفین فرض عدد ۲ را اضافه می‌کنیم، داریم:

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

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

$2k+2<2^{k}+1==2<(2^{k})x22^{k}==2<2^{k}(21)==2<2^{k}$

مشاهده می‌شود نامساوی برای k>2 همواره درست است و چون تمامی روابط برگشت پذیرند، لذا برقرار بوده و به این ترتیب حکم برای هر عدد طبیعی برقرار است.

منابع

• Rosen، Kenneth H. Discrete Mathematics and its Applications.

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