استقراء رياضي
الاستقراء الرياضي هو أحد أنواع البرهان الرياضي تستخدم عادة لبرهنة أنّ معادلة أو متباينة ما صحيحة لمجموعة لانهائية من الأعداد، كالأعداد الصحيحة. يعتمد البرهان على مبدأ وقوع أحجار الدومينو، ويتم على مرحلتين: في الأولى، يبرهن أنّ أوّل رقم في المجموعة يحقّق المطلوب، وفي الثانية نفرض أنّ المطلوب يتحقّق لعدد ما من المجموعة، ونبرهن، جبريًا، مثلاً، أنّه يتحقّق أيضًا للعدد الذي يليه في المجموعة استنادًا على الفرض وعلى الأساس.
يذكر، لمنع حصول التلابسات، أنّ الاستقراء الرياضي يختلف عن الاستنتاج الاستقرائي - فالأخير لا يعتبر برهانًا كافيًا ودقيقًا في عالم الرياضيات. الأصح هو القول أنّ الاستقراء الرياضي هو ضرب من الاستنتاج الاستدلالي (deductive reasoning).
ربما كانت محاورة أفلاطون سنة 370 قبل الميلاد قد حوت أول إثبات بالاستقراء الرياضي على الإطلاق. يمكن ملاحظة اثارالاستقراء الرياضي المبكرة في إثبات إقليدس بأن عدد الأعداد الأولية لانهائي. كما أن أول إثبات ضمني بالاستقراء الرياضي للمتوالية الحسابية كان على يد العربي البغدادي الكرخي حوالي سنة 1000 ميلادية, والذي استخدمها لإثبات نظرية ذات الحدين، مثلث باسكال، وصيغة المجموع لتكامل المكعبات.
كان إثباته هو الأول الذي استخدم المبدأين الأساسيين في الإثبات الاستقرائي, "وهما صواب التعبير من أجل "n" = 1 (لاحظ أن 1=1) واشتقاق الصواب من أجل "n" = "k" من تلك لقيمة "n" = "k" − 1. بالطبع الجزء الثاني غير نقدي لأنه بشكل أو باخر حجة الكراجي معكوسة; من هنا يبدأ الكراكي لـ"n" = 10 ومن ثم النزول حتى 1 بدلا من الاستمرار".
ومن بعده مباشرة جاء الحسن ابن الهيثم لإثبات مجموع قوى الدرجة الرابعة بطريقة الاستقراء. لقد قام بإثبات ذلك على أعداد صحيحة معينه فقط ولكن إثباته لهذه الأعداد كان بالاستقراء وشاملا. كما أن السموأل بن يحيى بن عباس كان أقرب إلى الإثبات الحديث بالاستقراء الرياضي عندما استخدمه في توسيع إثبات مثلث باسكال وذات الحدين.
الشكل العام والأبسط في الاستقراء الرياضي يثبت أن التعبير المتمثل في عدد طبيعي "n" يبقى صحيحا لجميع قيم "n". يتألف الإثبات من خطوتين:
يدعى الافتراض في خطوة الاستقراء بصحة التعبير لبعض قيم "n" بفرضية الاستقراء. لإجراء خطوة استقرائية فيجب فرض الفرضية الاستقرائية يثم استخدام هذا الفرض لاثبات التعبير لقيمة "n" + 1.
من السهل التمعن في تأثير الدومينو حيث يمكن شرحها كما يلي:
وبالتالي يمكن استنتاج أن جميع قطع الدومينو سوف تسقط وهذا أمر محتوم.
يمكن استخدام الاستقراء الرياضي لاثبات أن التعبير:
يظل صحيحا لكل الأعداد الطبيعية "n". هذه العلاقة تعطي صيغة حساب مجاميع الأعداد الطبيعية من 1 إلى "n". ويتم إثباتها كما يلي:
لنسمي هذا التعبير ("P"("n".
تعادل ("P"(1 التعبير:
في الطرف الأيسر من المعادلة الحد الوحيد هو 1, وعليه يكون الطرف الأيسر واحد.
بما أن الطرفان متساويان, يصبح التعبير صحيح من أجل "n"=1. وبالتالي أمكن إثبات أن ("P"(1 صحيحة.
نفرض أن ("P"("n" صحيحة (لقيمة غير معينة "n"). وينبغي توضيح أن ("P"("n" + 1 صحيحة أي:
وباستخدام الفرضية ("P"("n" صحيحة يمكن إعادة صياغة الطرف الأيسر على الشكل:
إلى:
وسيبين لنا الجبر أن
وعليه نجد أن ("P"("n" + 1 في الحقيقة صحيحة.
وبما أنه تم إثبات كلا الأساسين وخطوة الاستقراء, فقد استطعنا الإثبات بالاستقراء الرياضي أن
في الواقع العملي تختلف هياكل الإثباتات بالاستقراء الرياضي وفقا لطبيعة الخاصية المرادإثباتها.
إذا أردنا أن نثبت تعبيرا ليس لكل الأعداد الطبيعية ولكن الأعداد أكبر من أو تساوي عدد معين "b", فأننا:
يمكن استعمال هذه الطريقة مثلا لإثبات أن 'n"> 2"n" من أجل "n" ≥ 3. ويمكن التعويض بمثال أكثر من ذلك لاثبات أن
بهذه الطريقة يمكننا اثبات أن ("P"("n" تظل صحيحة لجميع قيم "n" ≥1, أو حتى عند "n" ≥−5. هذا النوع من الاستقراء الرياضي هو في الحقيحة حالة خاصة من الشكل السابق لأنه إذا كان التعبير قيد الإثبات هو ("P"("n"فأن اثباته بهاتين القاعدتين مكافئ للاثبات بـ "P"("n" + "b") لجميع الأعداد الطبيعية "n" بالخطوتين الأولتين.
العديد من الدوال القياسية في الرياضيات بما فيها العوامل مثل "+" والعلاقات مثل "=", هي ثنائية في الحقيقة, بمعنى أن لها وسيطين أو حجتين. تمتلك هذه الدوال غالبا خواصا توسعها ضمنيا لأكثر من وسيطين. على سبيل المثال, عند ما يكون الجمع "a" + "b"
معرفا ومعلومابحيث يحقق خاصية التجميع ("a" + "b") + "c" = "a" + ("b" + "c"), فإن الجمع الثلاثي "a" + "b" + "c" يصبح منطقيا إما على الصورة "a" + "b") + "c") أو الصورة ("a" + ("b" + "c". بالمثل الكثير من البديهيات والنظريات الرياضية يمكن إقراره فقط على التحويلات الثنائية من العمليات والعلاقات, ومن ثم توسيعها ضمنيا لتحويلات أعلى.
لنفرض أننا نرغب بإثبات تعبيرا بطول نوني "n" عملية معرفة ضمنيا من العمليات الثنائية, باستعمال الاستقراء الرياضي. حينئذ, لن يكون غريبا أن الحالة "n" = 2 تحمل وزنا خاصا. هنا نسرد بعض الأمثلة:
في هذا المثال, العملية الثنائية المذكورة انفا هي عملية الضرب (من الدوال). تنص القاعدة المستخدمة غالبا في المشتقات والتي يتم تدريسها في علم التفاضل والتكامل على:
أو بصورة المشتق اللوغاريتمي
ويمكن تعميم هذا على مضاريب "n" من الدوال.
أو بصورة المشتق اللوغاريتمي
في كل حد من حدود "n" على الشكل المألوف, يكون هناك فقط واحدا من المعاملات مشتقا والباقي لا.
عند إثبات هذه الحقيقة بالاستقراء الرياضي, سيكون اختيار "n" = 0 مبتذلا, ,formula_13 (لأن الضرب الخالي هو 1, والجمع الخالي هو 0).
كما أن اختيار "n" = 1 سيكون عاديا أيضا., formula_14 وفي كل "n" ≥ 3, يكون من السهل إثباتها من الحالة السابقة "n" − 1. تكمن الصعوبة الفعلية في حالة "n" = 2 وهذا هو السبب وراء نصها في قاعدة الضرب القياسية.
في هذا المثال, العملية الثنائية انفة الذكر هي علاقة مكافئة مطبقة على الأحصنة, بحيث أن كل حصانين يكونان متكافئان إذا كان لهما نفس اللون. الحجة في الاساس مماثلة لماسبق, ولكن الحالة الحرجة "n" = 2 تفشل, مسببة النقاش الداخلي غير مسموح به.
في أواسط القرن العشرين, كانت هناك عبارات عامية تعبر عن فكرة أن هنالك شيء مختلف عن المألوف وبشكل غير متوقع "ذلك من لون اخر!". افترض جورج بوليا التمرين التالي: ابحث عن الخطأ في هذا النقاش, والذي يزعم أن يثبت بالاستقراء الرياضي بأن جميع الأحصنة لها نفس اللون:
باستهلال الاستقراء عند 1, تكون الحالة "n" = 1 مبتذلة (فأي حصان له لون واحد كونه نفسه), والخطوة الاستقرائية صحيحة لكل الحالات "n" ≥ 3. ولكن, يكون منطق الخطوة الاستقرائية خاطئا عندما "n" = 2.,وذلك لأن التعبير"المجموعتان تتداخلان" خاطئ. في الحقيقة, الحالة "n" = 2 هي لغز المسألة. لو استطاع أحدهم اثبات الحالة "n" = 2 لكانت الحالات الأعلى قد مرت بخاصية التعدي بنفس العلاقة المكافئة.
شكل آخر من أشكال الاستقراء وهو النزول اللانهائي, إحدى وسائل بيير دي فيرما المفضلة. هذه النوع من الإثبات يعمل بشكل عكسي, ويمكن أن يفترض نماذج مختلفة قليلا. على سبيل المثال, قد يبدأ ببيان أنه إذا كان التعبير صحيحا لعدد طبيعي "n" لزم أن يكون صحيحا أيضا لأعداد طبيعية أصغر "m" حيث ("m" < "n"). باستعمال الاستقراء الرياضي (ضمنيا) مع الفرضيات الاستقرائية بخطأ التعبير لجميع الأعداد الطبيعية أقل أو تساوي "m", يمكن الاستنتاج بأن التعبير لايمكن أن يكون صحيحا لأي عدد طبيعي "n".
توجد طريقة أخرى للتعميم, تدعى الاستقراء التام أو الاستقراء الشديد أو استقراء مجموعة جرعات, تنص على أنه في الخطوة الثانية يمكننا افتراض ليس بقاء صحة الشرط لقيم "n" = "m" فحسب بل أيضا لقيم "n" أقل أو تساوي "m".
ليس ضروريا ذكر حالة الأساس في الاستقرار التام كافتراض منفصل. عندما نأخذ بعين الاعتبار الحالة الأولى, فأن اعتبار صحة الشرط لجميع الحالات السابقة أمر صحيح لاداعي لذكره. فخطوة الاستقراء للاستقراء التام في هذه الحالة مقابلة لحالة الأساس في الاستقراء العادي. وعلى ذلك ينبغي للإثبات بخطوة الاستقراء في الاستقراء التام أن تكون قادرة على العمل مع شرط خالي شبيه لما سبق. الإثبات الأول في السابق ليس من هذا النوع (لكن يمكن تحويله).
إن الاستقراء التام مفيد جدا عندما يتطلب الأمر مراحل عديدة من فرضيات الاستقراء لكل خطوة على حدة. مثلا يمكن استخدام الاستقراء التام لتوضيح أن:
حيث formula_16 هو عدد فيبوناكسي النوني وformula_17 (النسبة الذهبية) وformula_18 جذور formula_19. باستعمال التعريف
formula_20, يمكن التحقق من المتطابقة السابقة مباشرة بالتفاضل والتكامل formula_21 إذا افترضنا صحتها لكل من formula_22 وformula_23. لاستكمال الإثبات, يجب تحيقيق المتطابقة باستخدام كلا حالتي الأساس "n" == 0 و"n" == 1.
يوجد اثبات آخر بالاستقراء الرياضي يستخدم الفرضيتين بصحة التعبير لكل قيم "n" الصغرى تماما. لنعتبر التعبير بأن "كل عدد طبيعي أكبر من 1 هو حاصل ضرب أعداد أولية", وبافتراض أنه بدلالة "m" > 1 يكون صحيحا لجميع قيم الصغرى "n" > 1. إذا كان "m" عدد أولي فمؤكد أنه حاصل ضرب أعداد أولية وإذا لم يكن كذلك, فإنه من التعبير حاصل ضرب: "m" = "n" "n",
حيث أن أي من المعاملات لا يساوي 1, وعليه ولا يساوي "m", وبالتالي كليهما أقل من "m". الآن يتم تطبيق فرضية الاستقراء على "n" و"n", وبالتالي فكل منهما حاصل ضرب أعداد أولية. ومن ثم "m" حاصل ضرب مضاريب أعداد أولية, أي ضرب أعداد أولية. لاحظ أن حالة الأساس "m" =2 لم يتم اعتبارها بشكل صريح مطلقا.
يمكن إعادة صياغة الخطوتين الأخيرتين في خطوة واحدة:
في الحقيقة هذا هو الشكل العام الغالب في الاستقراء الرياضي ويمكن أثبات أنه ليس صالحا لتعابير الأعداد الطبيعية فحسب بل لعناصر أي مجموعة مؤسسة جيدأ, وبتعبير آخر زمرة غير انعكاسية سلاسل تنازلية لانهائية.
عند تطبيق هذا النوع من الاستقراء على الترتيبات (التي تشكل ترتيب حسن وعليه صنف مؤسس جيدا), تدعى استقراء محدود ويعد اثباتا له أهميته في نظرية المجموعات والطوبولوجيا والمجالات الأخرى.
وبشكل عام يميز الاستقراء المحدود ثلاث حالات:
وبمعنى أدق, من اللازم في الاستقراء المحدود أن يتم إثبات الأساس, لأنه لاجدوى من حالة خاصة للاقتراح إذا كان "P" صحيحا لكل قيم "n" كبديهية الأعداد الطبيعية, انظر.
ومع ذلك, يمكن إثباته في بعض الأنظمة المنطقية. على سبيل المثال, يمكن إثباته إذا افترض أن:
لاشتقاق استقراء بسيط من هذه البديهيات, ينبغي أن نبين أنه إذا كانت formula_24 اقتراحا ما متوقعا لـ"n", إذا كان:
فإنformula_24 صحيحة لجميع قيم "n".
نبين أولا أنه إذا كانت formula_29 صحيحة لكل "k" < "m", فإن formula_30 صحيحة أيضا. إذا كانت "m" صفرا, فإن formula_30 صحيحة. إذا كانت "m" = "k" + 1, فإن formula_29 صحيحة لأن "k" < "m" وعليه formula_33 صحيحة مما يعني أن formula_30 صحيحة. الباقي يتبع من مبادئ الاستقراء المحدود (انظر أسفل).