مبدا استقراء رياضي

Mathematical induction principle - Principe d’induction mathématique

مبدأ الاستقراء الرياضي

 

مبدأ الاستقراء الرياضي principle of mathematical induction، هو أحد أساليب البرهان الرياضي، إذ يمكن بوساطته وبالتدريج (بالتتابع) إثبات صحة قضية ما P (n)، من أجل جميع قيم n₀ < n، انطلاقًا من إثبات صحتها من أجل قيمة معينة n₀ تأخذها n.

والإثبات يتمّ على خطوتين:

1) الخطوة الأساسية: التحقق من صحة القضية P (n) من أجل n₀ = n. (أي التحقق من إن P (n₀) صحيحة).

2) الخطوة الاستقرائية: إثبات إنه: «إذا كانت القضية صحيحة من أجل: n = k (حيث k ≥ n₀)، فإن القضية صحيحة من أجل n = k +1

أي إن صحة P (k) تقضي صحة P (k + 1).

فإذا كانت P (n₀) صحيحة فإن P (n₀ +1) صحيحة، وبالتالي P (n₀ +2) ومن ثم فإنP (n₀ +3) صحيحة وهكذا. أي إن P (n) صحيحة من أجل جميع قيم n₀ > n.

إن كلاً من الخطوتين (الأولى والثانية) أساسي في البرهان، ولا يمكن الاستغناء عن أي منهما. فالاعتماد على إحداها فقط يؤدي إلى الوقوع في الخطأ. مثلاً:

1) القضية:

 صحيحة من أجل n = 1، ولكنها غير صحيحة من أجل باقي قيم n. أي إن التحقق من صحتها من أجل n = 1 لا يكفي للبرهان على صحتها من أجل قيم n الأخرى.

2) القضية n = n +1 غير صحيحة، من أجل جميع قيم n. لكن الاعتماد على الخطوة الثانية فقط في البرهان تجعل منها قضية صحيحة، وهذا خطأ. فإذا فرض إنها صحيحة من أجل n = k فإنها صحيحة من أجل n = k +1. إذ إن k = k +1 يقضي أن k +1 = (k +1) +1.

مثال (1) إذا كانت القضية المطروحة P (n) هي:

فلإثبات صحة هذه القضية من أجل جميع قيم n ≥ 1 :

1) التحقق من أجل n = 1، إذ إن:

وبالتالي فإن P (1) صحيحة.

2) بفرض إنها صحيحة من أجل n = k يكون

وبالتالي

أي إنها صحيحة من أجل n = k +1. إذًا فهي صحيحة من أجل جميع قيم n ≥ 1.

مثال (3) لإثبات إن:

1) آـ القضية صحيحة من أجل n = 1، ذلك لأن

ب ـ إذا كانت القضية صحيحة من أجل n = k ≥ 1 أي:

فإن:

صحيحة. فهي صحيحة دوماً.

2) آـ القضية صحيحة من أجل n = 1، ذلك لأن

ب ـ إذا كانت القضية صحيحة من أجل n = k ≥ 1 أي:

فإن:

وبالتالي فهي صحيحة دوماً.

مثال (3) إن n2ⁿ > n² من أجل جميع قيم  n5≤n ،لإثبات ذلك:

1) إن القضية صحيحة عندما  n = 5n ذلك لأن n2⁵=32 > 5²=25

2) إذا كانت القضية صحيحة من أجل:n = k ≥ 5n، أي: k2^k > k² فإن: k2^k. 2 > 2k² > (k+1)² ذلك لأن: k2k² - (k +1)² = k² - 2k -1 = (k -1)² - 2 > 0 وبالتالي:^k2^k+1 > (k +1)² .فالقضية صحيحة من أجل جميع قيم .5 ≤ n

مثال (4) إن مجموع الأعداد الفردية من:1 إلى n2n -1 يساوي مربع عددها. أي إن n1+3+5+…+(2n-1)=n².إن:

1) القضية صحيحة من أجل n =1n. ذلك لأن n1=1²ⁿ.

2) إذا كانت القضية صحيحة من أجل n = k، أي: k1 + 3 + 5 +…+ (2k-1) = k²k فإنk1+3+5+…+(2k-1) + (2k+1)=k² + (2k+1) = (k+1)²k

فهي صحيحة دوماً.

مثال (5) إن:

لإثبات ذلك:

1) إن القضية صحيحة عندما:

n =1 ذلك لأن:

2) إذا كانت القضية صحيحة من أجل n = k، أي:

فإن:

فهي صحيحة دوماً.

أنور توفيق اللحام

مراجع للاستزادة:

ـ أنور اللحام، مبادئ الجبر الخطي (منشورات جامعة دمشق، 1994).

- BERTRAND RUSSELL, Introduction to Mathematical Philosophy (Rutledge 1993).

- DONALD KNUTH, The Art of Computer Programming, Volume 1, Fundamental Algorithms (Addison-Wesley, 1997).

---

- التصنيف : الرياضيات و الفلك - النوع : علوم - المجلد : المجلد السابع عشر - رقم الصفحة ضمن المجلد : 622 مشاركة :