استقراء رياضي

Mathematical induction - Induction mathématique

الاستقراء الرياضي

خالد حلاوة

الاستقراء الرياضي (أو الإثبات بالتدريج) mathematical induction طريقة من طرائق الإثبات في الرياضيّات، لها أهميّة كبيرة وتطبيقات عديدة. يُعنى الاستقراء الرياضي بإثبات أنّ قضيّةً ما، تابعةً لمتحوّلٍ طبيعي صحيحةٌ أيّاً كان العدد الطبيعي.

يصعب حصر مجالات تطبيق الاستقراء الرياضي، فالمتحوّل يمكن أن يكون عدد نقاطٍ في مستوٍ، أو بُعد فضاءٍ شعاعيّ في الجبر الخطّي، أو عدد مراحل إجرائيّة ما. يُستخدم هذا المبدأ أيضاً في إثبات الكثير من النتائج في التحليل والهندسة والجبر الخطّي ونظريّة الأعداد وغيرها، وكذلك في صياغة بعض التعريفات ذات الطبيعة التدريجيّة.

تعتمد طريقة الاستقراء الرياضي على المبرهنة الآتية :

لتكن مجموعة جزئيّة من مجموعة الأعداد الطبيعيّة N تحقّق العلاقة ( 1).

عندئذٍ E = N.

وينتج من المبرهنة السابقة مباشرةً التكافؤ المنطقي المبين في العلاقة (2).

يمثّل هذا التكافؤ أساس الإثبات بالاستقراء الرياضي، ويجرى ذلك بإثبات أنّ القضيّة صحيحة عند كلّ الأعداد الطبيعيّة، وذلك بالخطوتين الآتيتين:

الأولى (نقطة البداية): التحقّق من صحّة القضيّة عند الصفر أي. (يُمكن أن تكون البداية عند أو ).

الثانية (خطوة الاستقراء): التحقّق من أنّه إذا كانت القضيّة صحيحة عند فهي صحيحة عند أي .

يُمكن تمثيل الاستقراء الرياضي بسقوط أحجار الدومينو، فسقوط الحجر الأوّل يؤدّي إلى سقوط كلّ الأحجار الأخرى، وذلك لأنّ سقوط أيّ حجر يتسبب بسقوط الحجر الذي يليه.

لابد من ملاحظة ما يأتي:

- إنّ مبدأ الاستقراء الرياضيّ خاص بمجموعة الأعداد الطبيعيّة N، وله علاقة ببُنية هذه المجموعة، ولا يمكن تطبيقه على مجموعات أخرى إلاّ إذا كانت بنيتها مشابهة لبنية N.

- لا يجوز خلط مبدأ الاستقراء الرياضي مع الحدس، فالأخير ليس إثباتاً رياضياً.

- على الرغم من بساطة مبدأ الاستقراء الرياضي يجب عدم إغفال أيّ شرط من شروطه. فصحّة القضيّة عند نقطة البداية مهمّة، وكذلك خطوة الاستقراء التي يجب الانتباه إلى أنها صحيحة انطلاقاً من نقطة البداية.

تطبيقات وأمثلة:

1 - مجموع الأعداد الطبيعيّة بين الصفر و.

لإثبات صحّة القضيّة

تُتّبع الخطوات الآتية:

- أيّاً كان العدد الطبيعي يرمز بالرمز إلى المساواة

- إنّ المساواة صحيحة عند الصفر لأن

- بفرض صحّة، يتوجب إثبات صحّة. حيث إن:

ومن ثمَّ صحيحة.

2 - مثال من نظريّة الأعداد:

أيّاً كان يُرمز بالرمز إلى القضيّة:

« يقسم العدد »

فيكون:

صحيحة لأنّ يقسم العدد .

- ليكن ، وبفرض صحّة أي يقسم. ومن ثمَّ:

وهذا يعني أنّ يقبل القسمة على .

وتكون بذلك القضيّة صحيحة أيّاً كان .

3.منشور الكرخي-نيوتن:

ليكن و عددين حقيقيّين. أيّاً كان العدد الطبيعي يرمز بالرمز إلى المساواة:

حيث هو عدد التوافيق المكوّنة من عنصراً منتقى من عنصراً.

•إنّ القضيّة صحيحة عند الصفر لأنّ

•بافتراض صحّة ينبغي إثبات صحّة . حيث إن:

ومن ثمَّ صحيحة. بذلك تكون صحيحة أيّاً كان .

4.برج هانوي:

ليكنعدداً طبيعيّاً غير معدوم، و A وB وC ثلاثة أعمدة، و قرصاً أقطارها متباينة مثنى مثنى، ومنضّدة فوق بعضها على العمود، ومرتّبة تنازليّاً بحيث يكون القرص الأكبر في الأسفل، كما هو مبيّن في الشكل ( 1).

الشكل ( 1): مسألة برج هانوي

المطلوب هو نقل هذه الأقراص إلى العمود بحيث تحافظ على ترتيبها وفق قواعد اللعبة الآتية:

- في كلّ حركة يمكن نقل قرص واحد فقط.

- لا يمكن وضع قرص فوق قرص أصغر منه.

الحلّ : يمكن حلّ هذه المسألة بالاستقراء الرياضي كما يأتي:

- الحل بديهي عندما .

- بافتراض أنّه يوجد حلّ للمسألة عند . ليكن هنالك قرصاً مرتّباً على العمود كما هو مبيّن في الشكل (1)، يمكن نقل الـ قرصاً الصغيرة من إلى باستخدام طريقة الحلّ عند، ثم نقل القرص الكبير إلى العمود، وبعد ذلك نقل الـ قرصاً المتبقّية إلى العمود .

يتضح أنّ للمسألة حلاًّ وذلك أيّاً كان .
من جهة أخرى، إذا رُمز بالرمز إلى عدد الخطوات اللاّزمة لحلّ المسألة يكون ، و . وعليه يُمكن التأكّد بسهولة أنّه أيّاً كان العدد فإنّ.

5 - مسألة الصرّاف الآلي:

يمكن إثبات أنّه يُمكن تشكيل أيّ مبلغ نقدي يزيد على ، باستخدام قطع نقديّة من فئتي و، وذلك بالتحقّق من خطوتي الاستقراء الرياضي.

- عندما يكون يُشكّل المبلغ بقطعتين من فئة .

- بافتراض تشكيل المبلغ باستخدام القطع من فئتي و. فإذا كان ضمن هذه القطع قطعةٌ من فئة يُستبدل ثلاث قطع من فئة بالقطعة من فئة 5 وبذلك يمكن الحصول على المبلغ n+1. أمّا إذا كانت كلّ القطع من فئة (عددها أكبر من اثنتين) فيمكن استبدال قطعة من فئة بقطعتين من فئة 2، وبذلك يمكن الحصول أيضاً على المبلغ .

6 - عدد أقطار مضلّع محدّب:

بفرض عدد أقطار مضلّع محدّب له رأساً.

- يكون .

- من جهة أخرى، أيّاً كان يمكن كتابة ما يلي: ، ومن ثمَّ يمكن التحقّق بسهولة أنّ

أشكال أخرى للاستقراء الرياضي:

ثمة أشكال معدّلة عن الاستقراء الرياضي يُمكن الاستفادة منها بحسب طبيعة المسألة المطروحة.

لتكن قضيّة تابعة لـ .

1 - ليكن ، إذا تحقّق الشرطان:

- .

- أيّاً كان فإنّ .

عندئذٍ يتحقق . تسمح هذه الطريقة بإثبات بعض القضايا ابتداءً من أو أو أي عدد آخر.

2 - إذا تحقّق الشرطان :

- .

- أيّاً كان فإنّ .

عندئذٍ تكون القضيّة صحيحة. وتجدر الإشارة إلى أنّ إثبات خطوة الاستقراء في هذه الحالة أسهل.

3 - إذا تحقّق الشرطان :

- و.

- أيّاً كان فإنّ .

عندئذٍ تكون القضيّة صحيحة. تجدر الإشارة إلى أنّ خطوة الاستقراء في هذه الحالة ثنائيّة، لذلك تُسمّى هذه الطريقة الاستقراء الثنائي الخطوة.

4.إذا تحقّقت الشروط :

- .

- أيّاً كان فإنّ.

- أيّاً كان فإنّ .

عندئذٍ يكون .

مراجع للاستزادة: - D. Applebaum, Probability and Information: An Integrated Approach, Cambridge University Press, 2008. - D. S. Gunderson, Handbook of Mathematical Induction: Theory and Applications, CRC Press, 2010. - H. Zhang, Automated Mathematical Induction, Kluwer Academic, 1996.

 

---

- المجلد : المجلد الثاني مشاركة :