عرض مصدر استقراء رياضي

[[ملف:Dominoeffect.png|thumb||300px|يمكن توصيف الاستقراء الرياضي بالنظر إلى التأثيرات المتعاقبة عند سقوط [[تأثير الدومينو|الدومينو]].]]
'''الاستقراء الرياضي''' {{إنك|Mathematical induction}} هو أحد أنواع [[برهان رياضي|البرهان الرياضي]] تستخدم عادة لبرهنة أنّ معادلة أو متباينة ما صحيحة ل[[مجموعة (رياضيات)|مجموعة]] لانهائية من الأعداد، ك[[عدد صحيح|الأعداد الصحيحة]]. يعتمد البرهان على مبدأ وقوع أحجار [[دومينو|الدومينو]]، ويتم على مرحلتين: في الأولى، يبرهن أنّ '''أوّل رقم''' في المجموعة يحقّق المطلوب، وفي الثانية نفرض أنّ المطلوب يتحقّق لعدد ما من المجموعة، ونبرهن، جبريًا، مثلاً، أنّه يتحقّق أيضًا للعدد الذي يليه في المجموعة استنادًا على '''الفرض''' وعلى '''الأساس'''.

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

== تاريخ ==
ربما كانت [[محاورة أفلاطون|محاورة]] [[أفلاطون]] سنة 370 [[قبل الميلاد]] قد حوت أول إثبات بالاستقراء الرياضي على الإطلاق.<ref>[http://me.nmsu.edu/~aseemath/1465_04_3.PDF Mathematical Induction: The Basis Step of Verification and Validation in a Modeling and Simulation Course]</ref> يمكن ملاحظة اثارالاستقراء الرياضي المبكرة في إثبات [[إقليدس]] بأن عدد [[الأعداد الأولية]] [[لانهائي]].<ref name="Induction Bussey">Cajori (1918), p.&nbsp;197<blockquote>"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."</blockquote></ref> كما أن أول [[إثبات رياضي|إثبات]] ضمني بالاستقراء الرياضي [[متوالية حسابية|للمتوالية الحسابية]] كان على يد [[العرب]]ي [[بغداد|البغداد]]ي [[الكرخي]] حوالي سنة 1000 ميلادية, والذي استخدمها لإثبات [[نظرية ذات الحدين]]، [[مثلث باسكال]]، وصيغة المجموع [[تكامل|لتكامل]] [[مكعب عدد|المكعبات]].<ref>Katz (1998), p. 255: <blockquote>"فكرة هامة أخرى قدمها  [[الكرخي]] وعمل عليها [[السموأل بن يحيى المغربي]] كانت أن [[حجة]] استقرائية تتعامل مع تعاقب معين من الأعداد.</blockquote></ref>
كان إثباته هو الأول الذي استخدم المبدأين الأساسيين في الإثبات الاستقرائي, "وهما [[صواب]] التعبير من أجل ''n'' = 1 (لاحظ أن 1=1<sup>3</sup>) واشتقاق الصواب من أجل ''n'' = ''k''  من تلك لقيمة ''n'' = ''k''&nbsp;−&nbsp;1. بالطبع الجزء الثاني غير نقدي لأنه بشكل أو باخر حجة الكراجي معكوسة; من هنا يبدأ الكراكي لـ''n'' = 10 ومن ثم النزول حتى  1 بدلا من الاستمرار".<ref>Katz (1998), p. 255: <blockquote>"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<sup>3</sup>) and the deriving of the truth for ''n'' = ''k'' from that of ''n'' = ''k''&nbsp;−&nbsp;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."</blockquote></ref><ref>{{MacTutor|id=Al-Karaji|title=Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji}}
{{quote|"Al-Karaji also uses a form of mathematical induction in his arguments, although he certainly does not give a rigorous exposition of the principle."}}</ref>
ومن بعده مباشرة جاء الحسن ابن الهيثم لإثبات مجموع قوى الدرجة الرابعة بطريقة الاستقراء. لقد قام بإثبات ذلك على أعداد صحيحة معينه فقط ولكن إثباته لهذه الأعداد كان بالاستقراء وشاملا. كما أن [[السموأل بن يحيى بن عباس]] كان أقرب إلى الإثبات الحديث بالاستقراء الرياضي عندما استخدمه في توسيع إثبات مثلث باسكال وذات الحدين.

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

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

== فرضية الدومينو ==
من السهل التمعن في [[تأثير الدومينو]] حيث يمكن شرحها كما يلي:

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

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

== مثال ==
يمكن استخدام الاستقراء الرياضي لاثبات أن التعبير:
: <math>1 + 2 + \cdots + n = \frac{n(n + 1)}{2}</math>

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

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

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

:<math>1 = \frac{1\cdot(1 + 1)}{2}\,.</math>
في الطرف الأيسر من المعادلة الحد الوحيد هو 1, وعليه يكون الطرف الأيسر واحد.

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

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

نفرض أن (''P''(''n'' صحيحة (لقيمة غير معينة ''n''). وينبغي توضيح أن (''P''(''n'' + 1 صحيحة أي:
:<math>1 + 2 + \cdots + n + (n+1) = \frac{(n+1)((n+1) + 1)}{2}</math>
وباستخدام الفرضية (''P''(''n'' صحيحة يمكن إعادة صياغة الطرف الأيسر على الشكل:

:<math>(1 + 2 + \cdots + n) + (n+1) = \frac{(n+1)((n+1) + 1)}{2}</math>

إلى:

:<math>\frac{n(n + 1)}{2} + (n+1) = \frac{(n+1)((n+1) + 1)}{2}\,.</math>

وسيبين لنا الجبر أن
{{إظهار|(انقر "إظهار" في اليمين لإظهار التفاصيل أو "إخفاء" لإخفاءها.)
|
: <math>
\begin{align}
\frac{n(n + 1)}{2} + (n+1) & = (n+1)\left(\frac n 2 + 1 \right) \\
& = (n+1)\left(\frac n 2 + \frac 2 2 \right) \\
& = (n+1)\left(\frac{n+2}{2}  \right) \\
& = \frac{(n+1)(n+2)}{2} \\
& = \frac{(n+1)((n+1) + 1)}{2}.
\end{align}
</math>
}}
وعليه نجد أن  (''P''(''n'' + 1 في الحقيقة صحيحة.

وبما أنه تم إثبات كلا الأساسين وخطوة الاستقراء, فقد استطعنا الإثبات بالاستقراء الرياضي أن
 (''P''(''n'' صحيحة لـ''جميع'' الأعداد الطبيعية.

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

=== البدء عند رقم اخر ===
إذا أردنا أن نثبت تعبيرا ليس لكل الأعداد الطبيعية ولكن الأعداد أكبر من أو تساوي عدد معين ''b'', فأننا:
# نبين أن التعبير يظل صحيحا عندما ''n'' = ''b''.
# نبين أنه إن كان التعبير صحيحا من أجل  ''n'' = ''m'' ≥ ''b''  فإن هذا التعبير سيبقى صحيحا من أجل ''n'' = ''m'' + 1.

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

:<math>{n^n \over 3^n} < n! < {n^n \over 2^n}\mbox{ for }n\ge 6.</math>

بهذه الطريقة يمكننا اثبات أن (''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 تحمل وزنا خاصا. هنا نسرد بعض الأمثلة:

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

:<math>(fg)' = f'g + g'f. \!</math>

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

:<math>(fg)'/ (fg) = f'/f + g'/g. \!</math>

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

:<math>(f_1 f_2 f_3 \cdots f_n)' \!</math>

::<math>= (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').</math>

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

:<math>(f_1 f_2 f_3 \cdots f_n)'/(f_1 f_2 f_3 \cdots f_n) \!</math>

::<math>= (f_1'/f_1) + (f_2'/f_2) + (f_3'/f_3) + \cdots + (f_n'/f_n).</math>

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

عند إثبات هذه الحقيقة بالاستقراء الرياضي, سيكون اختيار ''n'' = 0 مبتذلا, ,<math>(1)' = 0 \!</math>  (لأن الضرب الخالي هو 1, والجمع الخالي هو 0).
كما أن اختيار ''n'' = 1 سيكون عاديا أيضا., <math>f_1' = f_1' \!.</math> وفي كل ''n'' ≥ 3, يكون من السهل إثباتها من الحالة السابقة ''n'' − 1. تكمن الصعوبة الفعلية في حالة ''n'' = 2 وهذا هو السبب وراء نصها في قاعدة الضرب القياسية.

==== مثال: إثبات بويالا بأنه لايوجد "حصان من لون اخر" ====

في هذا المثال, العملية الثنائية انفة الذكر هي علاقة مكافئة مطبقة على الأحصنة, بحيث أن كل حصانين يكونان متكافئان إذا كان لهما نفس اللون. الحجة في الاساس مماثلة لماسبق, ولكن الحالة الحرجة ''n''&nbsp;=&nbsp;2  تفشل, مسببة النقاش الداخلي غير مسموح به.
في أواسط القرن العشرين, كانت هناك عبارات عامية تعبر عن فكرة أن هنالك شيئ مختلف عن المألوف وبشكل غير متوقع "'''ذلك''' من لون اخر!". افترض [[جورج بوليا]] التمرين التالي: ابحث عن الخطأ في هذا النقاش, والذي يزعم أن يثبت بالاستقراء الرياضي بأن جميع الأحصنة لها نفس اللون:

* الأساس: إن كان هناك حصان واحد فقط, فسيكون هنالك لون واحد فقط.
* خطوة الاستقراء: نفرض بالاستقراء أنه في أي مجموعة مكونة من ''n'' من الأحصنة, يوجد لون واحد فقط. والان للنظر إلى إي مجموعة بها ''n''&nbsp;+&nbsp;1 من الأحصنة. لتكن أرقامها: 1, 2, 3,..., ''n'', ''n''&nbsp;+&nbsp;1. ولنعتبر المجموعات {1, 2, 3,..., ''n''} و{2, 3, 4,..., ''n''&nbsp;+&nbsp;1}. كل منها محموعة من ''n''  من الأحصنة فقط, وعليه فإن في كل منها يوجد لون واحد فقط. ولكن المجموعتان تتداخلان, وبالتالي يجب أن يكون هناك لون واحد فقط بين كل الأحصنة''n''&nbsp;+&nbsp;1.

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

=== النزول اللانهائي ===
{{رئيسي|نزول لانهائي}}
شكل اخر من أشكال الاستقراء وهو النزول اللانهائي, إحدى وسائل [[بير فيرمات]] المفضلة. هذه النوع من الإثبات يعمل بشكل عكسي, ويمكن أن يفترض نماذج مختلفة قليلا. على سبيل المثال, قد يبدأ ببيان أنه إذا كان التعبير صحيحا لعدد طبيعي ''n''  لزم أن يكون صحيحا أيضا لأعداد طبيعية أصغر ''m'' حيث (''m'' &lt; ''n''). باستعمال الاستقراء الرياضي (ضمنيا) مع الفرضيات الاستقرائية بخطأ التعبير لجميع الأعداد الطبيعية أقل أو تساوي ''m'', يمكن الاستنتاج بأن التعبير لايمكن أن يكون صحيحا لأي عدد طبيعي ''n''.

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

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

:<math> \operatorname{F}(n) = \frac{(\varphi_+)^n - (\varphi_-)^n}{(\varphi_+) - (\varphi_-)}</math>

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

يوجد اثبات اخر بالاستقراء الرياضي يستخدم الفرضيتين بصحة التعبير '''لكل''' قيم ''n'' الصغرى تماما. لنعتبر التعبير بأن "كل [[عدد طبيعي]] أكبر من 1 هو حاصل ضرب أعداد أولية", وبافتراض أنه بدلالة ''m'' &gt; 1  يكون صحيحا لجميع قيم الصغرى ''n'' &gt; 1. إذا كان ''m'' [[عدد أولي]] فمؤكد أنه حاصل ضرب أعداد أولية وإذا لم يكن كذلك, فإنه من التعبير حاصل ضرب: ''m'' = ''n''<sub>1</sub> ''n''<sub>2</sub>, 

حيث أن أي من المعاملات لا يساوي 1, وعليه ولا يساوي ''m'', وبالتالي كليهما أقل من ''m''. الآن يتم تطبيق فرضية الاستقراء على ''n''<sub>1</sub> و''n''<sub>2</sub>,  وبالتالي فكل منهما حاصل ضرب أعداد أولية. ومن ثم ''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''.

لاشتقاق استقراء بسيط من هذه البديهيات, ينبغي أن نبين أنه إذا كانت <math>P(n) \,</math>  اقتراحا ما متوقعا لـ''n'', إذا كان:
* <math>P(0) \,</math>  صحيحة 
* عندما تكون <math>P(k)\,</math> صحيحة فإن <math>P(k+1)\,</math> صحيحة أيضا
فإن<math>P(n) \,</math>  صحيحة لجميع قيم ''n''.

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

== إنظر أيضًا ==

* [[مبرهنة التوافيق]]
* [[معاودة]]
* [[استقراء هيكلي]]
* [[معاودة (علوم حاسوب)]]
* [[استنتاج استقرائي]]

== المصادر والملاحظات ==
{{ثبت_المراجع}}

{{بوابة رياضيات}}

{{وصلة مقالة جيدة|de}}

[[تصنيف:رياضيات]]
[[تصنيف:منطق رياضي]]

{{وصلة مقالة مختارة|he}}

[[az:Riyazi Induksiya]]
[[bg:Математическа индукция]]
[[bn:গাণিতিক আরোহ বিধি]]
[[ca:Demostració per inducció]]
[[cs:Matematická indukce]]
[[da:Induktion (matematik)]]
[[de:Vollständige Induktion]]
[[el:Μαθηματική επαγωγή]]
[[en:Mathematical induction]]
[[eo:Matematika indukto]]
[[es:Inducción matemática]]
[[fa:استقرای ریاضی]]
[[fi:Matemaattinen induktio]]
[[fr:Raisonnement par récurrence]]
[[he:אינדוקציה מתמטית]]
[[hu:Teljes indukció]]
[[id:Induksi matematika]]
[[is:Þrepun]]
[[it:Principio d'induzione]]
[[ja:数学的帰納法]]
[[ko:수학적 귀납법]]
[[lt:Matematinė indukcija]]
[[mk:Индукција]]
[[ml:ഗണിതീയ ആഗമനം]]
[[ms:Induksi matematik]]
[[nl:Inductie (wiskunde)]]
[[nn:Matematisk induksjon]]
[[no:Matematisk induksjon]]
[[pl:Indukcja matematyczna]]
[[pt:Indução matemática]]
[[ro:Inducție matematică]]
[[ru:Математическая индукция]]
[[simple:Mathematical induction]]
[[sk:Matematická indukcia]]
[[sl:Matematična indukcija]]
[[sr:Математичка индукција]]
[[sv:Matematisk induktion]]
[[tr:Matematiksel tümevarım]]
[[uk:Математична індукція]]
[[zh:数学归纳法]]
[[zh-min-nan:Sò͘-ha̍k kui-la̍p-hoat]]