استقراء رياضي
المحتويات
- وسيبين لنا الجبر أن
- عندما تكون صحيحة فإن صحيحة أيضا
- تاريخ
- مثال
- أو بصورة المشتق اللوغاريتمي
- استقراء تام
- فرضية الدومينو
- البناء من n = 2
- إثبات أو إعادة صياغة الاستقراء الرياضي
- مثال: قاعدة الضرب للمشتقة
- استقراء محدود
- النزول اللانهائي
- أو بصورة المشتق اللوغاريتمي
- معاودة
- أشكال مختلفة
- ستسقط حجرة الدومينو الإولى
- الوصف
- البدء عند رقم اخر

قبل الخوض في التفاصيل، الاستقراء الرياضي هو أحد أنواع البرهان الرياضي تستعمل عادة لبرهنة أنّ معادلة أو متباينة ما صحيحة لمجموعة لانهائية من الأعداد، كالأعداد الصحيحة. يعتمد البرهان على مبدأ وقوع أحجار الدومينو، ويتم على مرحلتين: في الأولى، يبرهن أنّ أوّل رقم في المجموعة يحقّق المطلوب، وفي الثانية نفرض أنّ المطلوب يتحقّق لعدد ما من المجموعة، ونبرهن، جبريًا، مثلاً، أنّه يتحقّق كذلك للعدد الذي يليه في المجموعة استنادًا على الفرض وعلى الأساس. وفيما يلي تفاصيل أوسع عن ذلك.
من جانب آخر، يذكر، لمنع حصول التلابسات، أنّ الاستقراء الرياضي يختلف عن الاستنتاج الاستقرائي - فالأخير لا يعتبر برهانًا كافيًا ودقيقًا في عالم الرياضيات. الأصح هو القول أنّ الاستقراء الرياضي هو ضرب من الاستنتاج الاستدلالي (deductive reasoning).
وسيبين لنا الجبر أن
من جانب آخر، وبما أنه تم إثبات كلا الأساسين وخطوة الاستقراء، فقد استطعنا الإثبات بالاستقراء الرياضي أن
وعليه نجد أن (P(n + 1 في الحقيقة صحيحة.
(P(n صحيحة لـجميع الأعداد الطبيعية.
عندما تكون صحيحة فإن صحيحة أيضا
فإن صحيحة لجميع قيم n.
انظر كذلك
من جانب آخر، نبين أولا أنه إذا كانت صحيحة لكل k < m, فإن صحيحة كذلك. إذا كانت m صفرا، فإن صحيحة. إذا كانت m = k + 1, فإن صحيحة لأن k < m وعليه صحيحة مما يعني أن صحيحة. الباقي يتبع من مبادئ الاستقراء المحدود (انظر أسفل).
تاريخ
في هذا الإطار، كان إثباته هو الأول الذي استعمل المبدأين الأساسيين في الإثبات الاستقرائي، "وهما صواب التعبير من أجل n = 1 (لاحظ أن 1=13) واشتقاق الصواب من أجل n = k من تلك لقيمة n = k − 1. بالطبع الجزء الثاني غير نقدي لأنه بشكل أو باخر حجة الكراجي معكوسة; من هنا يبدأ الكراكي لـn = 10 ومن ثم النزول حتى 1 بدلا من الاستمرار".
ومن ناحية أخرى، ربما كانت محاورة أفلاطون سنة 370 قبل الميلاد قد حوت أول إثبات بالاستقراء الرياضي على الإطلاق. يمكن ملاحظة اثارالاستقراء الرياضي المبكرة في إثبات إقليدس بأن عدد الأعداد الأولية لانهائي. كما أن أول إثبات ضمني بالاستقراء الرياضي للمتوالية الحسابية كان على يد العربي البغدادي الكرخي نحو سنة 1000 ميلادية، والذي استعملها لإثبات نظرية ذات الحدين، مثلث باسكال، وصيغة المجموع لتكامل المكعبات.
من جانب آخر، ومن بعده مباشرة جاء الحسن ابن الهيثم لإثبات مجموع قوى الدرجة الرابعة بطريقة الاستقراء. لقد قام بإثبات ذلك على أعداد صحيحة معينه فقط ولكن إثباته لهذه الأعداد كان بالاستقراء وشاملا. كما أن السموأل بن يحيى بن عباس كان أقرب إلى الإثبات الحديث بالاستقراء الرياضي عندما استعمله في توسيع إثبات مثلث باسكال وذات الحدين.
مثال
يمكن استخدام الاستقراء الرياضي لاثبات أن التعبير:
- لنسمي هذا التعبير (P(n.
- الأساس: لنوضح أن التعبير صحيح من أجل n = 1.
- تعادل (P(1 التعبير:
- في الطرف الأيسر من المعادلة الحد الوحيد هو 1, وعليه يكون الطرف الأيسر واحد.
وفي هذا السياق، يظل صحيحا لكل الأعداد الطبيعية n. هذه العلاقة تعطي صيغة حساب مجاميع الأعداد الطبيعية من 1 إلى n. ويتم إثباتها كما يلي:
ومن ناحية أخرى، خطوة الاستقراء: تبين أنه إذا كانت (P(n صحيحة، فإن (P(n + 1 صحيحة كذلك. يتم ذلك على النحو الاتي.
وعلى صعيد آخر، بما أن الطرفان متساويان، يصبح التعبير صحيح من أجل n=1. وبالتالي أمكن إثبات أن (P(1 صحيحة.
- نفرض أن (P(n صحيحة (لقيمة غير معينة n). وينبغي توضيح أن (P(n + 1 صحيحة أي:
- وباستخدام الفرضية (P(n صحيحة يمكن إعادة صياغة الطرف الأيسر على الشكل:
- إلى:
أو بصورة المشتق اللوغاريتمي
ومن جهة أخرى، باستهلال الاستقراء عند 1, تكون الحالة n = 1 مبتذلة (فأي حصان له لون واحد كونه نفسه), والخطوة الاستقرائية صحيحة لكل الحالات n ≥ 3. ولكن، يكون منطق الخطوة الاستقرائية خاطئا عندما n = 2., وذلك لأن التعبير«المجموعتان تتداخلان» خاطئ. في الحقيقة، الحالة n = 2 هي لغز المسألة. لو استطاع أحدهم اثبات الحالة n = 2 لكانت الحالات الأعلى قد مرت بخاصية التعدي بنفس العلاقة المكافئة.
وفي هذا السياق، عند إثبات هذه الحقيقة بالاستقراء الرياضي، سيكون اختيار n = 0 مبتذلا، (لأن الضرب الخالي هو 1, والجمع الخالي هو 0).
وفي هذا السياق، في كل حد من حدود n على الشكل المألوف، يكون هناك فقط واحدا من المعاملات مشتقا والباقي لا.
من جهة ثانية، كما أن اختيار n = 1 سيكون عاديا كذلك., وفي كل n ≥ 3, يكون من السهل إثباتها من الحالة السابقة n − 1. تكمن الصعوبة الفعلية في حالة n = 2 وهذا هو السبب وراء نصها في قاعدة الضرب القياسية.
مثال: إثبات بويالا بأنه لايوجد "حصان من لون اخر
ومن ناحية أخرى، في أواسط القرن العشرين، كانت هناك عبارات عامية تعبر عن فكرة أن هنالك شيء مختلف عن المألوف وبشكل غير متوقع «ذلك من لون اخر!». افترض جورج بوليا التمرين التالي: ابحث عن الخطأ في هذا النقاش، والذي يزعم أن يثبت بالاستقراء الرياضي بأن جميع الأحصنة لها نفس اللون:
وفي هذا السياق، الأساس: إن كان هناك حصان واحد فقط، فسيكون هنالك لون واحد فقط.
ومن جهة أخرى، في هذا المثال، العملية الثنائية انفة الذكر هي علاقة مكافئة مطبقة على الأحصنة، بحيث أن كل حصانين يكونان متكافئان إذا كان لهما نفس اللون. الحجة في الاساس مماثلة لماسبق، ولكن الحالة الحرجة n = 2 تفشل، مسببة النقاش الداخلي غير مسموح به.
وفي هذا الصدد، خطوة الاستقراء: نفرض بالاستقراء أنه في أي مجموعة مكونة من n من الأحصنة، يوجد لون واحد فقط. والان للنظر إلى إي مجموعة بها n + 1 من الأحصنة. لتكن أرقامها: 1, 2, 3,..., n, n + 1. ولنعتبر المجموعات {1, 2, 3,..., n} و{2, 3, 4,..., n + 1}. كل منها محموعة من n من الأحصنة فقط، وعليه فإن في كل منها يوجد لون واحد فقط. ولكن المجموعتان تتداخلان، وبالتالي يجب أن يكون هناك لون واحد فقط بين كل الأحصنةn + 1.
استقراء تام
وفي السياق ذاته، خطوة الاستقراء : تبين أنه إذا كانت و صحيحة، فإن صحيحة كذلك. يتم ذلك على النحو الاتي.
وفي هذا السياق، يوجد اثبات آخر بالاستقراء الرياضي يستعمل الفرضيتين بصحة التعبير لكل قيم n الصغرى تماما. لنعتبر التعبير بأن «كل عدد طبيعي أكبر من 1 هو حاصل ضرب أعداد أولية», وبافتراض أنه بدلالة m > 1 يكون صحيحا لجميع قيم الصغرى n > 1. إذا كان m عدد أولي فمؤكد أنه حاصل ضرب أعداد أولية وإذا لم يكن كذلك، فإنه من التعبير حاصل ضرب: m = n1 n2,
من جهة ثانية، حيث أن أي من المعاملات لا يساوي 1, وعليه ولا يساوي m, وبالتالي كليهما أقل من m. الآن يتم تطبيق فرضية الاستقراء على n1 وn2, وبالتالي فكل منهما حاصل ضرب أعداد أولية. ومن ثم m حاصل ضرب مضاريب أعداد أولية، أي ضرب أعداد أولية. لاحظ أن حالة الأساس m =2 لم يتم اعتبارها بشكل صريح مطلقا.
وفي هذا السياق، توجد طريقة أخرى للتعميم، تدعى الاستقراء التام أو الاستقراء الشديد أو استقراء مجموعة جرعات, تنص على أنه في الخطوة الثانية يمكننا افتراض ليس بقاء صحة الشرط لقيم n = m فحسب بل كذلك لقيم n أقل أو تساوي m.
إضافةً إلى ذلك، إن الاستقراء التام مفيد جدا عندما يتطلب الأمر مراحل عديدة من فرضيات الاستقراء لكل خطوة على حدة. مثلا يمكن استخدام الاستقراء التام لتوضيح أن:
علاوةً على ذلك، ليس ضروريا ذكر حالة الأساس في الاستقرار التام كافتراض منفصل. عندما نأخذ بعين الاعتبار الحالة الأولى، فأن اعتبار صحة الشرط لجميع الحالات السابقة أمر صحيح لاداعي لذكره. فخطوة الاستقراء للاستقراء التام في هذه الحالة مقابلة لحالة الأساس في الاستقراء العادي. وعلى ذلك ينبغي للإثبات بخطوة الاستقراء في الاستقراء التام أن تكون قادرة على العمل مع شرط خالي شبيه لما سبق. الإثبات الأول في السابق ليس من هذا النوع (لكن يمكن تحويله).
ومن جهة أخرى، حيث هو عدد فيبوناكسي النوني و (النسبة الذهبية) و جذور . باستعمال التعريف ، يمكن التحقق من المتطابقة السابقة مباشرة بالتفاضل والتكامل إذا افترضنا صحتها لكل من و. لاستكمال الإثبات، يجب تحقيق المتطابقة باستخدام كلا حالتي الأساس و .
الأساس: لنوضح أن التعبير صحيح من أجل و :
فرضية الدومينو
من السهل التمعن في تأثير الدومينو حيث يمكن شرحها كما يلي:
البناء من n = 2
ومن جهة أخرى، الكثير من الدوال القياسية في الرياضيات بما فيها العوامل مثل "+" والعلاقات مثل "=", هي ثنائية في الحقيقة، بمعنى أن لها وسيطين أو حجتين. تمتلك هذه الدوال غالبا خواصا توسعها ضمنيا لأكثر من وسيطين. مثلًا، عند ما يكون الجمع a + bمعرفا ومعلومابحيث يحقق خاصية التجميع (a + b) + c = a + (b + c), فإن الجمع الثلاثي a + b + c يصبح منطقيا إما على الصورة a + b) + c) أو الصورة (a + (b + c. بالمثل الكثير من البديهيات والنظريات الرياضية يمكن إقراره فقط على التحويلات الثنائية من العمليات والعلاقات، ومن ثم توسيعها ضمنيا لتحويلات أعلى.
من جهة ثانية، لنفرض أننا نرغب بإثبات تعبيرا بطول نوني n عملية معرفة ضمنيا من العمليات الثنائية، باستعمال الاستقراء الرياضي. حينئذ، لن يكون غريبا أن الحالة n = 2 تحمل وزنا خاصا. هنا نسرد بعض الأمثلة:
إثبات أو إعادة صياغة الاستقراء الرياضي
وفي هذا الصدد، لاشتقاق استقراء بسيط من هذه البديهيات، ينبغي أن نبين أنه إذا كانت اقتراحا ما متوقعا لـn, إذا كان:
صحيحة
- مجموعة الأعداد الطبيعية هي ذات ترتيب حسن.
- كل عدد طبيعي إما صفر، أو n+1 لعدد طبيعي أكبر من n.
- لعدد طبيعي n يكون n+1 أكبر من n.
وعلى صعيد آخر، غالبا ما يتم نص مبدأ الاستقراء الرياضي كبديهية الأعداد الطبيعية، انظر.
في هذا الإطار، ومع ذلك، يمكن إثباته في بعض الأنظمة المنطقية. مثلًا، يمكن إثباته إذا افترض أن:
مثال: قاعدة الضرب للمشتقة
وعلى صعيد آخر، في هذا المثال، العملية الثنائية المذكورة انفا هي عملية الضرب (من الدوال). تنص القاعدة المستعملة غالبا في المشتقات والتي يتم تدريسها في علم التفاضل والتكامل على:
استقراء محدود
في هذا الإطار، عند تطبيق هذا النوع من الاستقراء على الترتيبات (التي تشكل ترتيب حسن وعليه صنف مؤسس جيدا), تدعى استقراء محدود ويعد اثباتا له أهميته في نظرية المجموعات والطوبولوجيا والمجالات الأخرى.
في هذا الإطار، عندما يكون m عنصرا صغريا أي أنه لايوجد عنصر أصغر منm عندما تمتلك m سلفا مباشرا، أي مجموعة من العناصر أقل من m لها عنصر أعظمي.
وبشكل عام يميز الاستقراء المحدود ثلاث حالات:
يمكن إعادة صياغة الخطوتين الأخيرتين في خطوة واحدة:
عندما لا يكون لـm سلفا مباشرا، أي أن m تدعى نهاية ترتيبية.
وفي هذا السياق، في الحقيقة هذا هو الشكل العام الغالب في الاستقراء الرياضي ويمكن أثبات أنه ليس صالحا لتعابير الأعداد الطبيعية فحسب بل لعناصر أي مجموعة مؤسسة جيدأ، وبتعبير آخر زمرة غير انعكاسية <تلك التي لا تحوي سلاسل تنازلية لانهائية.
وفي هذا الصدد، بتوضيح أنه إذا كان التعبير صحيحا لجميع قيم n <m فإن نفس التعبير صحيح كذلك من أجل n = m.
كذلك، وبمعنى أدق، من اللازم في الاستقراء المحدود أن يتم إثبات الأساس، لأنه لاجدوى من حالة خاصة للاقتراح إذا كان P صحيحا لكل قيم n <m, فإن P صحيحا في m.
النزول اللانهائي
من جهة ثانية، شكل آخر من أشكال الاستقراء وهو النزول اللانهائي، إحدى وسائل بيير دي فيرما المفضلة. هذه النوع من الإثبات يعمل بشكل عكسي، ويمكن أن يفترض نماذج مختلفة قليلا. مثلًا، قد يبدأ ببيان أنه إذا كان التعبير صحيحا لعدد طبيعي n لزم أن يكون صحيحا كذلك لأعداد طبيعية أصغر m حيث (m < n). باستعمال الاستقراء الرياضي (ضمنيا) مع الفرضيات الاستقرائية بخطأ التعبير لجميع الأعداد الطبيعية أقل أو تساوي m, يمكن الاستنتاج بأن التعبير لايمكن أن يكون صحيحا لأي عدد طبيعي n.
أو بصورة المشتق اللوغاريتمي
ويمكن تعميم هذا على مضاريب n من الدوال.
معاودة
- معاودة (علوم حاسوب)
- استنتاج استقرائي
- هيرمان كراسمان
- المصادر والملاحظات
أشكال مختلفة
وفي هذا الصدد، في الواقع العملي تختلف هياكل الإثباتات بالاستقراء الرياضي بحسب طبيعة الخاصية المرادإثباتها.
ستسقط حجرة الدومينو الإولى
علاوةً على ذلك، وبالتالي يمكن استنتاج أن جميع قطع الدومينو سوف تسقط وهذا أمر محتوم.
كلما سقطت حجرة دومينو تلتها أخرى،
الوصف
ومن ناحية أخرى، خطوة الاستقراء: لإثبات أنه إذا كان التعبير صحيحا لبعض قيم n, فإن التعبير صحيح كذلك عندما تعويض n + 1 في n.
الأساس: لإثبات صحة التعبير عند n = 0 أو n = 1 غالباً.
وفي هذا الصدد، الشكل العام والأبسط في الاستقراء الرياضي يثبت أن التعبير المتمثل في عدد طبيعي n يبقى صحيحا لجميع قيم n. يتألف الإثبات من خطوتين:
ومن ناحية أخرى، يدعى الافتراض في خطوة الاستقراء بصحة التعبير لبعض قيم n بفرضية الاستقراء. لإجراء خطوة استقرائية فيجب فرض الفرضية الاستقرائية يثم استخدام هذا الفرض لاثبات التعبير لقيمة n + 1.
البدء عند رقم اخر
نبين أن التعبير يظل صحيحا عندما n = b.
من جهة ثانية، بهذه الطريقة يمكننا اثبات أن (P(n تظل صحيحة لجميع قيم n ≥1, أو حتى عند n ≥−5. هذا النوع من الاستقراء الرياضي هو في الحقيحة حالة خاصة من الشكل السابق لأنه إذا كان التعبير قيد الإثبات هو (P(nفأن اثباته بهاتين القاعدتين مكافئ للاثبات بـ P(n + b) لجميع الأعداد الطبيعية n بالخطوتين الأولتين.
وفي السياق ذاته، يمكن استعمال هذه الطريقة مثلا لإثبات أن 'n2> 2n من أجل n ≥ 3. ويمكن التعويض بمثال أكثر من ذلك لاثبات أن
علاوةً على ذلك، إذا أردنا أن نثبت تعبيرا ليس لكل الأعداد الطبيعية ولكن الأعداد أكبر من أو تساوي عدد معين b, فأننا:
كذلك، نبين أنه إن كان التعبير صحيحا من أجل n == m ≥ b فإن هذا التعبير سيبقى صحيحا من أجل n == m + 1.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟