ریاضی علم کامپیوتر - استقرا

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

به مثال زیر توجه کنید:

1=12

1+3=22

1+3+5=32

حال آیا می توانیم بگوییم مجموع x عدد فرد که از یک تا 2x-1 می باشند برابر است با x2 ؟ پس از قسمت زیر به این سوال پاسخ خواهیم داد.

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

استقرای ضعیف

فرض کنید n عددی طبیعی باشد و p(n)حکمی در مورد اعداد طبیعی باشد. فرض کنید:

1- P(1) باشد.

2- اگر p(k) درست باشد آنگاه p(k+1) نیز باشد.

آنگاه حکم p(n) برای همه ی اعداد طبیعی درست می باشد.

حال می خواهیم به حدسی که در قسمت بالا زدیم پاسخ دهیم:

حکم به شکل مقابل است:

p(n):1+3+5+…+(2n-1)=n2

داریم:

p(1):1=12

فرض می کنیم p(k) درست است. بنابراین:

1+3+5+…+(2k-1)=k2

چون می خواهیم حکم را برای k+1 اثبات کنیم لذا به طرفین p(k) ، عبارت 2(k+1)-1 را می افزاییم. داریم:

1+3+5+…+(2k+1)=k2+(2k+1)=(k+1)2

بنابراین حکم برای n=k+1 نیز درست است. پس بنابر استقرای ضعیف حکم برای هر عدد طبیعی n درست می باشد.

ریاضی علم کامپیوتر - استقرا

مطالب مشابه :

آموزش ورود به سامانه سجاد

نمونه سوال ریاضی علم کامپیوتر - استقرا

سامانه دانشجویی جدید جهاد دانشگاهی اهواز

برنامه هفتگی