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

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

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

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

تاريخ

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

الوصف

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

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

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

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

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

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

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

مثال

يمكن استعمال الاستقراء الرياضي لاثبات حتى التعبير:

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

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

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

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

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

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

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

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

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

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

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

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

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

إلى:

{\displaystyle {\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. ويمكن التعويض بمثال أكثر من ذلك لاثبات أن

{\displaystyle {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 تحمل وزنا خاصا. هنا نسرد بعض الأمثلة:

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

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

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

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

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

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

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

{\displaystyle =(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 ').

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

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

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

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

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

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

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

حيث ${\displaystyle \varphi _{- =(1-{\sqrt {5 )/2$

يوجد اثبات اخر بالاستقراء الرياضي يستخدم الفرضيتين بصحة التعبير لكل قيم 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.

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

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

فإن ${\displaystyle P(n)\,$ سليمة لجميع قيم n.

نبين أولا أنه إذا كانت ${\displaystyle P(k)\,$ سليمة لكل k < m, فإن ${\displaystyle P(m)\,$ سليمة أيضا. إذا كانت m صفرا, فإن ${\displaystyle P(m)\,$ سليمة. إذا كانت m = k + 1, فإن ${\displaystyle P(k)\,$ سليمة لأن k < m وعليه ${\displaystyle P(k+1)\,$ سليمة مما يعني حتى ${\displaystyle 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 =عشرة 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."