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

يمكن توصيف الاستقراء الرياضي بالنظر إلى التأثيرات المتعاقبة عند سقوط الدومينو.

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

يذكر، لمنع حصول التباسات، أنّ الاستقراء الرياضي يختلف عن الاستنتاج الاستقرائي - فالأخير لا يعتبر برهانًا كافيًا ودقيقًا في عالم الرياضيات. الأصح هو القول أنّ الاستقراء الرياضي هو ضرب من الاستنتاج الاستدلالي (deductive reasoning).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

تاريخ

ربما كانت محاورة أفلاطون سنة 370 قبل الميلاد قد حوت أول إثبات بالاستقراء الرياضي على الإطلاق.^[1] يمكن ملاحظة اثارالاستقراء الرياضي المبكرة في إثبات إقليدس بأن عدد الأعداد الأولية لانهائي.^[2] كما أن أول إثبات ضمني بالاستقراء الرياضي للمتوالية الحسابية كان على يد العربي البغدادي الكرخي حوالي سنة 1000 ميلادية, والذي استخدمها لإثبات نظرية ذات الحدين، مثلث باسكال، وصيغة المجموع لتكامل المكعبات.^[3] كان إثباته هو الأول الذي استخدم المبدأين الأساسيين في الإثبات الاستقرائي, "وهما صواب التعبير من أجل n = 1 (لاحظ أن 1=1³) واشتقاق الصواب من أجل n = k من تلك لقيمة n = k − 1. بالطبع الجزء الثاني غير نقدي لأنه بشكل أو باخر حجة الكراجي معكوسة; من هنا يبدأ الكراكي لـn = 10 ومن ثم النزول حتى 1 بدلا من الاستمرار".^[4]^[5] ومن بعده مباشرة جاء الحسن ابن الهيثم لإثبات مجموع قوى الدرجة الرابعة بطريقة الاستقراء. لقد قام بإثبات ذلك على أعداد صحيحة معينه فقط ولكن إثباته لهذه الأعداد كان بالاستقراء وشاملا. كما أن السموأل بن يحيى بن عباس كان أقرب إلى الإثبات الحديث بالاستقراء الرياضي عندما استخدمه في توسيع إثبات مثلث باسكال وذات الحدين.

الوصف

الشكل العام والأبسط في الاستقراء الرياضي يثبت أن التعبير المتثل في عدد طبيعي n يبقى صحيحا لجميع قيم n. يتألف الإثبات من خطوتين:

الأساس: لإثبات صحة التعبير عند n = 0 أو n = 1.
خطوة الاستقراء: لإثبات أنه إذا كان التعبير صحيحا لبعض قيم n, فإن التعبير صحيح أيضا عندما تعويض n + 1 في n.

يدعى الافتراض في خطوة الاستقراء بصحة التعبير لبعض قيم n بفرضية الاستقراء. لإجراء خطوة استقرائية فيجب فرض الفرضية الاستقرائية يثم استخدام هذا الفرض لاثبات التعبير لقيمة n + 1.

فرضية الدومينو

من السهل التمعن في تأثير الدومينو حيث يمكن شرحها كما يلي:

ستسقط حجرة الدومينو الإولى
كلما سقطت حجرة دومينو تلتها أخرى,

وبالتالي يمكن استنتاج أن جميع قطع الدومينو سوف تسقط وهذا أمر محتوم.

مثال

يمكن استخدام الاستقراء الرياضي لاثبات أن التعبير:

1+2+\cdots +n={\frac {n(n+1)}{2}}

يظل صحيحا لكل الأعداد الطبيعية n. هذه العلاقة تعطي صيغة حساب مجاميع الأعداد الطبيعية من 1 إلى n. ويتم إثباتها كما يلي:

لنسمي هذا التعبير (P(n.

الأساس: لنوضح أن التعبير صحيح من أجل n = 1.

تعادل (P(1 التعبير:

1={\frac {1\cdot (1+1)}{2}}\,.

في الطرف الأيسر من المعادلة الحد الوحيد هو 1, وعليه يكون الطرف الأيسر واحد.

بما أن الطرفان متساويان, يصبح التعبير صحيح من أجل n=1. وبالتالي أمكن إثبات أن (P(1 صحيحة.

خطوة الاستقراء: تبين أنه إذا كانت (P(n صحيحة, فإن (P(n + 1 صحيحة أيضا. يتم ذلك على النحو الاتي.

نفرض أن (P(n صحيحة (لقيمة غير معينة n). وينبغي توضيح أن (P(n + 1 صحيحة أي:

1+2+\cdots +n+(n+1)={\frac {(n+1)((n+1)+1)}{2}}

وباستخدام الفرضية (P(n صحيحة يمكن إعادة صياغة الطرف الأيسر على الشكل:

(1+2+\cdots +n)+(n+1)={\frac {(n+1)((n+1)+1)}{2}}

إلى:

{\frac {n(n+1)}{2}}+(n+1)={\frac {(n+1)((n+1)+1)}{2}}\,.

وسيبين لنا الجبر أن قالب:إظهار وعليه نجد أن (P(n + 1 في الحقيقة صحيحة.

وبما أنه تم إثبات كلا الأساسين وخطوة الاستقراء, فقد استطعنا الإثبات بالاستقراء الرياضي أن

(P(n صحيحة لـجميع الأعداد الطبيعية.

أشكال مختلفة

في الواقع العملي تختلف هياكل الإثباتات بالاستقراء الرياضي وفقا لطبيعة الخاصية المرادإثباتها.

البدء عند رقم اخر

إذا أردنا أن نثبت تعبيرا ليس لكل الأعداد الطبيعية ولكن الأعداد أكبر من أو تساوي عدد معين b, فأننا:

نبين أن التعبير يظل صحيحا عندما n = b.
نبين أنه إن كان التعبير صحيحا من أجل n = m ≥ b فإن هذا التعبير سيبقى صحيحا من أجل n = m + 1.

يمكن استعمال هذه الطريقة مثلا لإثبات أن 'n² > 2n من أجل n ≥ 3. ويمكن التعويض بمثال أكثر من ذلك لاثبات أن

{n^{n} \over 3^{n}}<n!<{n^{n} \over 2^{n}}{\mbox{ for }}n\geq 6.

بهذه الطريقة يمكننا اثبات أن (P(n تظل صحيحة لجميع قيم n ≥1, أو حتى عند n ≥−5. هذا النوع من الاستقراء الرياضي هو في الحقيحة حالة خاصة من الشكل السابق لأنه إذا كان التعبير قيد الاثبات هو (P(nفأن اثباته بهاتين القاعدتين مكافئ للاثبات بـ P(n + b) لجميع الأعداد الطبيعية n بالخطوتين الأولتين.

البناء من n = 2

العديد من الدوال القياسية في الرياضيات بما فيها العوامل مثل "+" والعلاقات مثل "=", هي ثنائية في الحقيقة, بمعنى أن لها وسيطين أو حجتين. تمتلك هذه الدوال غالبا خواصا توسعها ضمنيا لأكثر من وسيطين. على سبيل المثال, عند ما يكون الجمع a + b معرفا ومعلومابحيث يحقق خاصية التجميع (a + b) + c = a + (b + c), فإن الجمع الثلاثي a + b + c يصبح منطقيا إما على الصورة a + b) + c) أو الصورة (a + (b + c. بالمثل الكثير من البديهيات والنظريات الرياضية يمكن إقراره فقط على التحويلات الثنائية من العمليات والعلاقات, ومن ثم توسيعها ضمنيا لتحويلات أعلى.

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

مثال: قاعدة الضرب للمشتقة

في هذا المثال, العملية الثنائية المذكورة انفا هي عملية الضرب (من الدوال). تنص القاعدة المستخدمة غالبا في المشتقات والتي يتم تدريسها في علم التفاضل والتكامل على:

(fg)'=f'g+g'f.\!

أو بصورة المشتق اللوغاريتمي

(fg)'/(fg)=f'/f+g'/g.\!

ويمكن تعميم هذا على مضاريب n من الدوال.

(f_{1}f_{2}f_{3}\cdots f_{n})'\!

=(f_{1}'f_{2}f_{3}\cdots f_{n})+(f_{1}f_{2}'f_{3}\cdots f_{n})+(f_{1}f_{2}f_{3}'\cdots f_{n})+\cdots +(f_{1}f_{2}\cdots f_{n-1}f_{n}').

أو بصورة المشتق اللوغاريتمي

(f_{1}f_{2}f_{3}\cdots f_{n})'/(f_{1}f_{2}f_{3}\cdots f_{n})\!

=(f_{1}'/f_{1})+(f_{2}'/f_{2})+(f_{3}'/f_{3})+\cdots +(f_{n}'/f_{n}).

في كل حد من حدود n على الشكل المألوف, يكون هناك فقط واحدا من المعاملات مشتقا والباقي لا.

عند إثبات هذه الحقيقة بالاستقراء الرياضي, سيكون اختيار n = 0 مبتذلا, , $(1)'=0\!$ (لأن الضرب الخالي هو 1, والجمع الخالي هو 0). كما أن اختيار n = 1 سيكون عاديا أيضا., $f_{1}'=f_{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.

باستهلال الاستقراء عند 1, تكون الحالة n = 1 مبتذلة (فأي حصان له لون واحد كونه نفسه), والخطوة الاستقرائية صحيحة لكل الحالات n ≥ 3. ولكن, يكون منطق الخطوة الاستقرائية خاطئا عندما n = 2.,وذلك لأن التعبير"المجموعتان تتداخلان" خاطئ. في الحقيقة, الحالة n = 2 هي لغز المسألة. لو استطاع أحدهم اثبات الحالة n = 2 لكانت الحالات الأعلى قد مرت بخاصية التعدي بنفس العلاقة المكافئة.

النزول اللانهائي

مقالة مفصلة: نزول لانهائي

شكل اخر من أشكال الاستقراء وهو النزول اللانهائي, إحدى وسائل بير فيرمات المفضلة. هذه النوع من الإثبات يعمل بشكل عكسي, ويمكن أن يفترض نماذج مختلفة قليلا. على سبيل المثال, قد يبدأ ببيان أنه إذا كان التعبير صحيحا لعدد طبيعي n لزم أن يكون صحيحا أيضا لأعداد طبيعية أصغر m حيث (m < n). باستعمال الاستقراء الرياضي (ضمنيا) مع الفرضيات الاستقرائية بخطأ التعبير لجميع الأعداد الطبيعية أقل أو تساوي m, يمكن الاستنتاج بأن التعبير لايمكن أن يكون صحيحا لأي عدد طبيعي n.

استقراء تام

توجد طريقة أخرى للتعميم, تدعى الاستقراء التام أو الاستقراء الشديد أو استقراء مجموعة جرعات, تنص على أنه في الخطوة الثانية يمكننا افتراض ليس بقاء صحة الشرط لقيم n = m فحسب بل أيضا لقيم n أقل أو تساوي m. ليس ضروريا ذكر حالة الأساس في الاستقرار التام كافتراض منفصل. عندما نأخذ بعين الاعتبار الحالة الأولى, فأن اعتبار صحة الشرط لجميع الحالات السابقة أمر صحيح لاداعي لذكره. فخطوة الاستقراء للاستقراء التام في هذه الحالة مقابلة لحالة الأساس في الاستقراء العادي. وعلى ذلك ينبغي للإثبات بخطوة الاستقراء في الاستقراء التام أن تكون قادرة على العمل مع شرط خالي شبيه لما سبق. الإثبات الأول في السابق ليس من هذا النوع (لكن يمكن تحويله).

إن الاستقراء التام مفيد جدا عندما يتطلب الأمر مراحل عديدة من فرضيات الاستقراء لكل خطوة على حدة. مثلا يمكن استخدام الاستقراء التام لتوضيح أن:

\operatorname {F} (n)={\frac {(\varphi _{+})^{n}-(\varphi _{-})^{n}}{(\varphi _{+})-(\varphi _{-})}}

حيث $\operatorname {F} (n)$ هو عدد فيبوناكسي النوني و $\varphi _{+}=(1+{\sqrt {5}})/2$ (النسبة الذهبية) و $\varphi _{-}=(1-{\sqrt {5}})/2$ جذور $\ x^{2}-x-1=0$ . باستعمال التعريف $\operatorname {F} (m+1)=\operatorname {F} (m)+\operatorname {F} (m-1)$ , يمكن التحقق من المتطابقة السابقة مباشرة بالتفاضل والتكامل $\operatorname {F} (m+1)$ إذا افترضنا صحتها لكل من $\operatorname {F} (m)$ و $\operatorname {F} (m-1)$ . لاستكمال الاثبات, يجب تحيقيق المتطابقة باستخدام كلا حالتي الأساس n = 0 وn = 1.

يوجد اثبات اخر بالاستقراء الرياضي يستخدم الفرضيتين بصحة التعبير لكل قيم n الصغرى تماما. لنعتبر التعبير بأن "كل عدد طبيعي أكبر من 1 هو حاصل ضرب أعداد أولية", وبافتراض أنه بدلالة m > 1 يكون صحيحا لجميع قيم الصغرى n > 1. إذا كان m عدد أولي فمؤكد أنه حاصل ضرب أعداد أولية وإذا لم يكن كذلك, فإنه من التعبير حاصل ضرب: m = n₁ n₂,

حيث أن أي من المعاملات لا يساوي 1, وعليه ولا يساوي m, وبالتالي كليهما أقل من m. الآن يتم تطبيق فرضية الاستقراء على n₁ وn₂, وبالتالي فكل منهما حاصل ضرب أعداد أولية. ومن ثم m حاصل ضرب مضاريب أعداد أولية, أي ضرب أعداد أولية. لاحظ أن حالة الأساس m =2 لم يتم اعتبارها بشكل صريح مطلقا.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

استقراء محدود

مقالة مفصلة: استقراء محدود

يمكن إعادة صياغة الخطوتين الأخيرتين في خطوة واحدة:

بتوضيح أنه إذا كان التعبير صحيحا لجميع قيم n < m فإن نفس التعبير صحيح أيضا من أجل n = m.

في الحقيقة هذا هو الشكل العام الغالب في الاستقراء الرياضي ويمكن أثبات أنه ليس صالحا لتعابير الأعداد الطبيعية فحسب بل لعناصر أي مجموعة مؤسسة جيدأ, وبتعبير اخر زمرة غير إنعكاسية < تلك التي لا تحوي سلاسل تنازلية لانهائية.

عند تطبيق هذا النوع من الاستقراء على الترتيبات (التي تشكل ترتيب حسن وعليه صنف مؤسس جيدا), تدعى استقراء محدود ويعد اثباتا له أهميته في نظرية المجموعة, التوبولوجي, والمجالات الأخرى. وبشكل عام يميز الاستقراء المحدود ثلاث حالات:

عندما يكون m عنصرا صغريا أي أنه لايوجد عنصر أصغر منm
عندما تمتلك m سلفا مباشرا, أي مجموعة من العناصر أقل من m لها عنصر أعظمي.
عندما لا يكون لـm سلفا مباشرا, أي أن m تدعى نهاية ترتيبية.

وبمعنى أدق, من اللازم في الاستقراء المحدود أن يتم إثبات الأساس, لأنه لاجدوى من حالة خاصة للاقتراح إذا كان P صحيحا لكل قيم n < m, فإن P صحيحا في m.

إثبات أو إعادة صياغة الاستقراء الرياضي

غالبا ما يتم نص مبدأ الاستقراء الرياضي كبديهية الأعداد الطبيعية, انظر. ومع ذلك, يمكن إثباته في بعض الأنظمة المنطقية. على سبيل المثال, يمكن إثباته إذا افترض أن:

مجموعة الأعداد الطبيعية هي ذات ترتيب حسن.
كل عدد طبيعي إما صفر, أو n+1 لعدد طبيعي أكبر من n.
لعدد طبيعي n يكون n+1 أكبر من n.

لاشتقاق استقراء بسيط من هذه البديهيات, ينبغي أن نبين أنه إذا كانت $P(n)\,$ اقتراحا ما متوقعا لـn, إذا كان:

$P(0)\,$ صحيحة
عندما تكون $P(k)\,$ صحيحة فإن $P(k+1)\,$ صحيحة أيضا

فإن $P(n)\,$ صحيحة لجميع قيم n.

نبين أولا أنه إذا كانت $P(k)\,$ صحيحة لكل k < m, فإن $P(m)\,$ صحيحة أيضا. إذا كانت m صفرا, فإن $P(m)\,$ صحيحة. إذا كانت m = k + 1, فإن $P(k)\,$ صحيحة لأن k < m وعليه $P(k+1)\,$ صحيحة مما يعني أن $P(m)\,$ صحيحة. الباقي يتبع من مبادئ الاستقراء المحدود (انظر أسفل).

إنظر أيضًا

المصادر والملاحظات

^ Mathematical Induction: The Basis Step of Verification and Validation in a Modeling and Simulation Course
^ Cajori (1918), p. 197
"The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite."
^ Katz (1998), p. 255:
"فكرة هامة أخرى قدمها الكرخي وعمل عليها السموأل بن يحيى المغربي كانت أن حجة استقرائية تتعامل مع تعاقب معين من الأعداد.
^ Katz (1998), p. 255:
"Al-Karaji's argument includes in essence the two basic components of a modern argument by induction, namely the truth of the statement for n = 1 (1 = 1³) and the deriving of the truth for n = k from that of n = k − 1. Of course, this second component is not explicit since, in some sense, al-Karaji's argument is in reverse; this is, he starts from n = 10 and goes down to 1 rather than proceeding upward. Nevertheless, his argument in al-Fakhri is the earliest extant proof of the sum formula for integral cubes."
^ O'Connor, John J.; Robertson, Edmund F., "Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji", MacTutor History of Mathematics archive, University of St Andrews .
"Al-Karaji also uses a form of mathematical induction in his arguments, although he certainly does not give a rigorous exposition of the principle."

الكلمات الدالة:

[1] Mathematical Induction: The Basis Step of Verification and Validation in a Modeling and Simulation Course

[Induction_Bussey-2] Cajori (1918), p. 197
"The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite."

[3] Katz (1998), p. 255:
"فكرة هامة أخرى قدمها الكرخي وعمل عليها السموأل بن يحيى المغربي كانت أن حجة استقرائية تتعامل مع تعاقب معين من الأعداد.

[4] Katz (1998), p. 255:
"Al-Karaji's argument includes in essence the two basic components of a modern argument by induction, namely the truth of the statement for n = 1 (1 = 1³) and the deriving of the truth for n = k from that of n = k − 1. Of course, this second component is not explicit since, in some sense, al-Karaji's argument is in reverse; this is, he starts from n = 10 and goes down to 1 rather than proceeding upward. Nevertheless, his argument in al-Fakhri is the earliest extant proof of the sum formula for integral cubes."

[5] O'Connor, John J.; Robertson, Edmund F., "Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji", MacTutor History of Mathematics archive, University of St Andrews .
"Al-Karaji also uses a form of mathematical induction in his arguments, although he certainly does not give a rigorous exposition of the principle."

[1]

[2]

[3]

[4]

[5]