تويت
مبدا استقراء رياضي
Mathematical induction principle - Principe d’induction mathématique
مبدأ الاستقراء الرياضي
مبدأ الاستقراء الرياضي principle of mathematical induction، هو أحد أساليب البرهان الرياضي، إذ يمكن بوساطته وبالتدريج (بالتتابع) إثبات صحة قضية ما P (n)، من أجل جميع قيم n0 < n، انطلاقًا من إثبات صحتها من أجل قيمة معينة n0 تأخذها n.
والإثبات يتمّ على خطوتين:
1) الخطوة الأساسية: التحقق من صحة القضية P (n) من أجل n0 = n. (أي التحقق من إن P (n0) صحيحة).
2) الخطوة الاستقرائية: إثبات إنه: «إذا كانت القضية صحيحة من أجل: n = k (حيث k ≥ n0)، فإن القضية صحيحة من أجل n = k +1
أي إن صحة P (k) تقضي صحة P (k + 1).
فإذا كانت P (n0) صحيحة فإن P (n0 +1) صحيحة، وبالتالي P (n0 +2) ومن ثم فإنP (n0 +3) صحيحة وهكذا. أي إن P (n) صحيحة من أجل جميع قيم n0 > 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) إن n2n > n2 من أجل جميع قيم n5≤n ،لإثبات ذلك:
1) إن القضية صحيحة عندما n = 5n ذلك لأن n25=32 > 52=25
2) إذا كانت القضية صحيحة من أجل:n = k ≥ 5n، أي: k2k > k2فإن: k2k. 2 > 2k2 > (k+1)2 ذلك لأن: k2k2 - (k +1)2 = k2 - 2k -1 = (k -1)2 - 2 > 0 وبالتالي:k2k+1 > (k +1)2 . فالقضية صحيحة من أجل جميع قيم .5 ≤ n
مثال (4) إن مجموع الأعداد الفردية من:1 إلى n2n -1 يساوي مربع عددها. أي إن n1+3+5+…+(2n-1)=n2. إن:
1) القضية صحيحة من أجل n =1n. ذلك لأن n1=12n.
2) إذا كانت القضية صحيحة من أجل n = k، أي: k1 + 3 + 5 +…+ (2k-1) = k2k فإنk1+3+5+…+(2k-1) + (2k+1)=k2 + (2k+1) = (k+1)2k
فهي صحيحة دوماً.
مثال (5) إن:
لإثبات ذلك:
1) إن القضية صحيحة عندما:
n =1 ذلك لأن:
2) إذا كانت القضية صحيحة من أجل n = k، أي:
فإن:
فهي صحيحة دوماً.
أنور توفيق اللحام
Mathematical induction principle - Principe d’induction mathématique
مبدأ الاستقراء الرياضي
مبدأ الاستقراء الرياضي principle of mathematical induction، هو أحد أساليب البرهان الرياضي، إذ يمكن بوساطته وبالتدريج (بالتتابع) إثبات صحة قضية ما P (n)، من أجل جميع قيم n0 < n، انطلاقًا من إثبات صحتها من أجل قيمة معينة n0 تأخذها n.
والإثبات يتمّ على خطوتين:
1) الخطوة الأساسية: التحقق من صحة القضية P (n) من أجل n0 = n. (أي التحقق من إن P (n0) صحيحة).
2) الخطوة الاستقرائية: إثبات إنه: «إذا كانت القضية صحيحة من أجل: n = k (حيث k ≥ n0)، فإن القضية صحيحة من أجل n = k +1
أي إن صحة P (k) تقضي صحة P (k + 1).
فإذا كانت P (n0) صحيحة فإن P (n0 +1) صحيحة، وبالتالي P (n0 +2) ومن ثم فإنP (n0 +3) صحيحة وهكذا. أي إن P (n) صحيحة من أجل جميع قيم n0 > 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) إن n2n > n2 من أجل جميع قيم n5≤n ،لإثبات ذلك:
1) إن القضية صحيحة عندما n = 5n ذلك لأن n25=32 > 52=25
2) إذا كانت القضية صحيحة من أجل:n = k ≥ 5n، أي: k2k > k2فإن: k2k. 2 > 2k2 > (k+1)2 ذلك لأن: k2k2 - (k +1)2 = k2 - 2k -1 = (k -1)2 - 2 > 0 وبالتالي:k2k+1 > (k +1)2 . فالقضية صحيحة من أجل جميع قيم .5 ≤ n
مثال (4) إن مجموع الأعداد الفردية من:1 إلى n2n -1 يساوي مربع عددها. أي إن n1+3+5+…+(2n-1)=n2. إن:
1) القضية صحيحة من أجل n =1n. ذلك لأن n1=12n.
2) إذا كانت القضية صحيحة من أجل n = k، أي: k1 + 3 + 5 +…+ (2k-1) = k2k فإنk1+3+5+…+(2k-1) + (2k+1)=k2 + (2k+1) = (k+1)2k
فهي صحيحة دوماً.
مثال (5) إن:
لإثبات ذلك:
1) إن القضية صحيحة عندما:
n =1 ذلك لأن:
2) إذا كانت القضية صحيحة من أجل n = k، أي:
فإن:
فهي صحيحة دوماً.
أنور توفيق اللحام