Mathematical induction

Mathematical induction is a method for proving that a statement $P(n)$ is true for every natural number $n$ , that is, that the infinitely many cases $P(0),P(1),P(2),P(3),\dots$ all hold. This is done by first proving a simple case, then also showing that if we assume the claim is true for a given case, then the next case is also true. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).

—Concrete Mathematics, page 3 margins.

A proof by induction consists of two cases. The first, the base case, proves the statement for $n=0$ without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case $n=k$ , then it must also hold for the next case $n=k+1$ . These two steps establish that the statement holds for every natural number $n$ . The base case does not necessarily begin with $n=0$ , but often with $n=1$ , and possibly with any fixed natural number $n=N$ , establishing the truth of the statement for all natural numbers $n\geq N$ .

The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction is an inference rule used in formal proofs, and is the foundation of most correctness proofs for computer programs.^[3]

Despite its name, mathematical induction differs fundamentally from inductive reasoning as used in philosophy, in which the examination of many cases results in a probable conclusion. The mathematical method examines infinitely many cases to prove a general statement, but it does so by a finite chain of deductive reasoning involving the variable $n$ , which can take infinitely many values. The result is a rigorous proof of the statement, not an assertion of its probability.^[4]

History

According to David E. Joyce, there is no evidence for the use of the principle of mathematical induction in Euclid’s writings.^[5] Fabio Acerbi in 2000 argues that Plato’s Parmenides (c. 370 BC) contains traces of an early implicit inductive proof.^[6] This interpretation has been challenged by Negrepontis and Farmaki in 2021, who further state that neither Plato nor any of the other Pythagoreans used the principle of mathematical induction.^[7]

The earliest implicit proof by mathematical induction was written by al-Karaji around 1000 AD, who applied it to arithmetic sequences to prove the binomial theorem and properties of Pascal's triangle. Whilst the original work was lost, it was later referenced by Al-Samawal al-Maghribi in his treatise al-Bahir fi'l-jabr (The Brilliant in Algebra) in around 1150 AD.^[8]^[9]^[10]

Katz says in his history of mathematics

Another important idea introduced by al-Karaji and continued by al-Samaw'al and others was that of an inductive argument for dealing with certain arithmetic sequences. Thus al-Karaji used such an argument to prove the result on the sums of integral cubes already known to Aryabhata [...] Al-Karaji did not, however, state a general result for arbitrary n. He stated his theorem for the particular integer 10 [...] His proof, nevertheless, was clearly designed to be extendable to any other integer. [...] 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.^[11]

In India, early implicit proofs by mathematical induction appear in Bhaskara's "cyclic method".^[12]

Another similar case (contrary to what Vacca has written, as Freudenthal carefully showed)^[13] was that of Francesco Maurolico in his Arithmeticorum libri duo (1575), who used the technique to prove that the sum of the first $n$ odd integers is $n 2$ .

The earliest rigorous use of induction was by Gersonides (1288–1344).^[14]^[15] The first explicit formulation of the principle of induction was given by Pascal in his Traité du triangle arithmétique (1665). Another Frenchman, Fermat, made ample use of a related principle: indirect proof by infinite descent.

The induction hypothesis was also employed by the Swiss Jakob Bernoulli, and from then on it became well known. The modern formal treatment of the principle came only in the 19th century, with George Boole,^[16]Augustus De Morgan, Charles Sanders Peirce,^[17]^[18]Giuseppe Peano, and Richard Dedekind.^[12]

Description

The simplest and most common form of mathematical induction infers that a statement involving a natural number $n$ (that is, an integer $n \geq 0$ or 1) holds for all values of $n$ . The proof consists of two steps:

The base case (or initial case): prove that the statement holds for 0, or 1.
The induction step (or inductive step, or step case): prove that for every $n$ , if the statement holds for $n$ , then it holds for $n + 1$ . In other words, assume that the statement holds for some arbitrary natural number $n$ , and prove that the statement holds for $n + 1$ .

The hypothesis in the induction step, that the statement holds for a particular $n$ , is called the induction hypothesis or inductive hypothesis. To prove the induction step, one assumes the induction hypothesis for $n$ and then uses this assumption to prove that the statement holds for $n + 1$ .

Authors who prefer to define natural numbers to begin at 0 use that value in the base case; those who define natural numbers to begin at 1 use that value.

Examples

Sum of consecutive natural numbers

Mathematical induction can be used to prove the following statement for all natural numbers $n\geq 0$ : $P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.$

This states a general formula for the sum of the natural numbers less than or equal to a given number; in fact an infinite sequence of statements: $0={\tfrac {(0)(0+1)}{2}}$ , $0+1={\tfrac {(1)(1+1)}{2}}$ , $0+1+2={\tfrac {(2)(2+1)}{2}}$ , etc.

Proposition. For every $n\in \mathbb {N}$ , we have that $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

Proof. Let $P(n)$ be the statement $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$ We give a proof by induction on $n$ .

Base case: Show that the statement holds for the smallest natural number $n = 0$ .

$P(0)$ is clearly true: $0={\tfrac {0(0+1)}{2}}\,.$

Induction step: Show that for every $k\geq 0$ , if $P(k)$ holds, then $P(k+1)$ also holds.

Assume the induction hypothesis that for a particular $k$ , the single case $n=k$ holds, meaning $P(k)$ is true: $0+1+\cdots +k={\frac {k(k+1)}{2}}.$ It follows that: $(0+1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1).$

Algebraically, the right hand side simplifies as: ${\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}.\end{aligned}}$

Equating the extreme left hand and right hand sides, we deduce that: $0+1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.$ That is, the statement $P(k+1)$ also holds true, establishing the induction step.

Conclusion: Since both the base case and the induction step have been proved as true, by mathematical induction the statement $P(n)$ holds for every natural number $n\geq 0$ . Q.E.D.

A trigonometric inequality

Induction is often used to prove inequalities. As an example, we prove that $\left|\sin nx\right|\leq n\left|\sin x\right|$ for any real number $x$ and natural number $n$ .

At first glance, it may appear that a more general version, $\left|\sin nx\right|\leq n\left|\sin x\right|$ for any real numbers $n,x$ , could be proven without induction; but the case ${\textstyle n={\frac {1}{2}},\,x=\pi }$ shows it may be false for non-integer values of $n$ . This suggests we examine the statement specifically for natural values of $n$ , and induction is the readiest tool.

Proposition. For any $x\in \mathbb {R}$ and $n\in \mathbb {N}$ , $\left|\sin nx\right|\leq n\left|\sin x\right|$ .

Proof. Fix an arbitrary real number $x$ , and let $P(n)$ be the statement $\left|\sin nx\right|\leq n\left|\sin x\right|$ . We induct on $n$ .

Base case: The calculation $\left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|$ verifies $P(0)$ .

Induction step: We show the implication $P(k)\implies P(k+1)$ for any natural number $k$ . Assume the induction hypothesis: for a given value $n=k\geq 0$ , the single case $P(k)$ is true. Using the angle addition formula and the triangle inequality, we deduce: ${\begin{aligned}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(angle addition)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(triangle inequality)}}\\&=\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\right|&&{\text{(induction hypothesis}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}$

يُظهر التفاوت بين الكميتين القصوى في الطرف الأيسر والطرف الأيمن أن $P(k+1)$ وهذا صحيح، مما يكمل خطوة الاستقراء.

الخلاصة: الاقتراح $P(n)$ ينطبق هذا على جميع الأعداد الطبيعية $n.$ QED

المتغيرات

عمليًا، غالبًا ما تُصاغ البراهين بالاستقراء بشكل مختلف، اعتمادًا على الطبيعة الدقيقة للخاصية المراد إثباتها. جميع أنواع الاستقراء هي حالات خاصة من الاستقراء المتسامي ؛ انظر أدناه .

الحالة الأساسية بخلاف 0 أو 1

إذا رغب المرء في إثبات عبارة، ليس لجميع الأعداد الطبيعية، ولكن فقط لجميع الأعداد $n$ الأكبر من أو تساوي عددًا معينًا $b$ ، فإن البرهان بالاستقراء يتكون مما يلي:

إثبات أن العبارة صحيحة عندما $n = b$ .
بإثبات أنه إذا كانت العبارة صحيحة لأي عدد $n \geq b$ ، فإن العبارة نفسها تنطبق أيضًا على $n + 1$ .

يمكن استخدام هذا، على سبيل المثال، لإظهار أن $2 ن \geq ن + 5$ لـ $ن \geq 3$ .

بهذه الطريقة، يمكن إثبات صحة العبارة $P (n)$ لجميع $قيم n \geq 1$ ، أو حتى لجميع $قيم n \geq -5$ . يُعد هذا الشكل من الاستقراء الرياضي حالة خاصة من الشكل السابق، لأنه إذا كانت العبارة المراد إثباتها هي $P (n)،$ فإن إثباتها باستخدام هاتين القاعدتين يُكافئ إثبات $P (n + b)$ لجميع الأعداد الطبيعية $n$ مع حالة أساسية للاستقراء تساوي $صفرًا$ . ^{[ 19 ]}

مثال: تكوين مبالغ الدولار باستخدام العملات المعدنية

لنفترض وجود كمية غير محدودة من العملات المعدنية من فئتي 4 و5 دولارات. يمكن استخدام الاستقراء الرياضي لإثبات أن أي مبلغ صحيح من الدولارات أكبر من أو يساوي $12$ دولارًا يمكن تكوينه من خلال مجموعة من هذه العملات. لنرمز بـ $S (k)$ إلى العبارة " يمكن تكوين $k$ دولارًا من خلال مجموعة من العملات المعدنية من فئتي 4 و5 دولارات". يمكن إثبات صحة $S (k)$ لجميع $قيم k \geq 12$ بالاستقراء الرياضي على $k$ كما يلي:

الحالة الأساسية: إثبات أن $S (k)$ صحيح لـ $k = 12$ أمر بسيط: خذ ثلاث عملات معدنية من فئة 4 دولارات.

Induction step: Given that $S (k)$ holds for some value of $k \geq 12$ (induction hypothesis), prove that $S (k + 1)$ holds, too. Assume $S (k)$ is true for some arbitrary $k \geq 12$ . If there is a solution for $k$ dollars that includes at least one 4-dollar coin, replace it by a 5-dollar coin to make $k + 1$ dollars. Otherwise, if only 5-dollar coins are used, $k$ must be a multiple of 5 and so at least 15; but then we can replace three 5-dollar coins by four 4-dollar coins to make $k + 1$ dollars. In each case, $S (k + 1)$ is true.

Therefore, by the principle of induction, $S (k)$ holds for all $k \geq 12$ , and the proof is complete.

In this example, although $S (k)$ also holds for ${\textstyle k\in \{4,5,8,9,10\}}$ , the above proof cannot be modified to replace the minimum amount of $12$ dollar to any lower value $m$ . For $m = 11$ , the base case is actually false; for $m = 10$ , the second case in the induction step (replacing three 5- by four 4-dollar coins) will not work; let alone for even lower $m$ .

Induction on more than one counter

It is sometimes desirable to prove a statement involving two natural numbers, $n$ and $m$ , by iterating the induction process. That is, one proves a base case and an induction step for $n$ , and in each of those proves a base case and an induction step for $m$ . See, for example, the proof of commutativity accompanying addition of natural numbers. More complicated arguments involving three or more counters are also possible.

Infinite descent

طريقة التناقص اللانهائي هي شكل من أشكال الاستقراء الرياضي استخدمها بيير دي فيرما . تُستخدم هذه الطريقة لإثبات أن عبارة $Q (n)$ خاطئة لجميع الأعداد الطبيعية $n$ . وتتمثل صيغتها التقليدية في إثبات أنه إذا كانت $Q (n)$ صحيحة لعدد طبيعي $n$ ، فإنها صحيحة أيضًا لعدد طبيعي أصغر منها $m$ . ولأنه لا توجد متتابعات تناقصية لانهائية من الأعداد الطبيعية، فإن هذا الوضع مستحيل، مما يُثبت ( بالتناقض ) أن $Q (n)$ لا يمكن أن تكون صحيحة لأي قيمة لـ $n$ .

يمكن التحقق من صحة هذه الطريقة من خلال مبدأ الاستقراء الرياضي المعتاد. باستخدام الاستقراء الرياضي على العبارة $P (n)$ المعرفة على أنها " $Q (m)$ خاطئة لجميع الأعداد الطبيعية $m$ الأقل من أو تساوي $n$ "، يتبين أن $P (n)$ صحيحة لجميع $قيم n$ ، مما يعني أن $Q (n)$ خاطئة لكل عدد طبيعي $n$ .

الاستقراء الرياضي المحدود

إذا أراد المرء إثبات أن الخاصية $P$ تنطبق على جميع الأعداد الطبيعية الأقل من أو تساوي $N$ ثابتة ، فإن إثبات أن $P$ تحقق الشروط التالية يكفي: ^{[ 20 ]}

$ينطبق الشرط P$ على الصفر،
لأي عدد طبيعي $x$ أقل من $N$ ، إذا تحققت $P$ لـ $x$ ، فإن $P$ تتحقق لـ $x + 1$

الاستقراء بالبادئة

يتطلب الشكل الأكثر شيوعًا للإثبات بالاستقراء الرياضي إثبات في خطوة الاستقراء أن $\forall k\,(P(k)\to P(k+1))$

وبناءً على ذلك، فإن مبدأ الاستقراء "يُسهّل" $تطبيق$ هذه الخطوة في الانتقال من $P (0)$ إلى $P (n)$ . ويمكن تسمية هذا "استقراء السلف" لأن كل خطوة تثبت شيئًا ما عن عدد ما انطلاقًا من شيء ما عن سلفه.

أحد المتغيرات المهمة في مجال التعقيد الحسابي هو "الاستقراء البادئ"، حيث يتم إثبات العبارة التالية في خطوة الاستقراء: $\forall k\,(P(k)\to P(2k)\land P(2k+1))$ أو ما يعادل ذلك $\forall k\,\left(P\!\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)$

ثم يقوم مبدأ الاستقراء بأتمتة عدد من تطبيقات هذا الاستدلال يبلغ لوغاريتم ₂ ن، وذلك للانتقال من $P$ $(0)$ إلى $P$ $($ $n$ $)$ . في الواقع، يُطلق عليه اسم "استقراء البادئة" لأن كل خطوة تثبت شيئًا ما عن عدد ما انطلاقًا من شيء ما عن "بادئة" ذلك العدد - والتي تتشكل عن طريق اقتطاع البت الأدنى من تمثيله الثنائي . ويمكن أيضًا اعتباره تطبيقًا للاستقراء التقليدي على طول ذلك التمثيل الثنائي.

إذا فُسِّر الاستقراء التقليدي القائم على السلف حسابيًا على أنه حلقة $من n$ خطوة، فإن الاستقراء القائم على البادئة يُقابل حلقة من log $-n$ خطوة. ولهذا السبب، فإن البراهين التي تستخدم الاستقراء القائم على البادئة "أكثر جدوى من الناحية البنائية" من البراهين التي تستخدم الاستقراء القائم على السلف.

يمكن لتقنية الاستقراء السابق محاكاة الاستقراء السابق بشكل بديهي على نفس العبارة. ويمكن للاستقراء السابق محاكاة الاستقراء السابق، ولكن على حساب زيادة تعقيد العبارة نحويًا (بإضافة مُكمِّم شامل محدود )، لذا فإن النتائج المهمة التي تربط الاستقراء السابق بالحسابات متعددة الحدود تعتمد على استبعاد المُكمِّمات غير المحدودة تمامًا، والحد من التناوب المسموح به بين المُكمِّمات الشاملة والوجودية المحدودة في العبارة. ^[²¹^]

يمكن للمرء أن يذهب بالفكرة خطوة أبعد: يجب على المرء أن يثبت $\forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)$ وبناءً على ذلك، فإن مبدأ الاستقراء "يُؤتمت" تطبيقات هذا الاستدلال من $لوغاريتم لوغاريتم ن في الانتقال من$ $P (0)$ إلى $P (n)$ . وقد استُخدم هذا الشكل من الاستقراء، على نحو مماثل، لدراسة الحوسبة المتوازية ذات الزمن اللوغاريتمي.

تحريض كامل (قوي)

هناك نوع آخر يُسمى الاستقراء الكامل ، أو استقراء مسار القيم ، أو الاستقراء القوي (على عكس الشكل الأساسي للاستقراء الذي يُعرف أحيانًا بالاستقراء الضعيف )، وهو يجعل خطوة الاستقراء أسهل في الإثبات باستخدام فرضية أقوى: حيث يتم إثبات العبارة $P(m+1)$ بافتراض أن $P(n)$ ينطبق هذا على جميع الأعداد الطبيعية $n$ أقل من $m+1$ على النقيض من ذلك، فإن الشكل الأساسي لا يفترض إلا $P(m)$ إن اسم "الاستقراء القوي" لا يعني أن هذه الطريقة يمكنها إثبات أكثر مما يمكن إثباته "الاستقراء الضعيف"، ولكنه يشير فقط إلى الفرضية الأقوى المستخدمة في خطوة الاستقراء.

في الواقع، يمكن إثبات أن الطريقتين متكافئتان، كما هو موضح أدناه. في هذا النوع من الاستقراء الكامل، لا يزال يتعين إثبات الحالة الأساسية. $P(0)$ بل وقد يكون من الضروري إثبات حالات إضافية مثل $P(1)$ قبل تطبيق الحجة العامة، كما في المثال أدناه لعدد فيبوناتشي $F_{n}$ .

على الرغم من أن الصيغة الموصوفة للتو تتطلب إثبات الحالة الأساسية، إلا أن هذا غير ضروري إذا كان بإمكان المرء إثبات $P(m)$ (بافتراض $P(n)$ لجميع المستويات الأدنى $n$ ) للجميع $m\geq 0$ هذه حالة خاصة من الاستقراء المتسامي كما هو موضح أدناه، على الرغم من أنها لم تعد مكافئة للاستقراء العادي. في هذه الصيغة، تُدمج الحالة الأساسية ضمن الحالة $m=0$ ، أين $P(0)$ وقد ثبت ذلك دون غيره $P(n)$ مفترض؛ قد تحتاج هذه الحالة إلى معالجة منفصلة، ولكن في بعض الأحيان ينطبق نفس المنطق على $m=0$ و $m>0$ مما يجعل البرهان أبسط وأكثر أناقة. ومع ذلك، في هذه الطريقة، من الضروري التأكد من أن برهان $P(m)$ لا يفترض ضمنيًا أن $m>0$ على سبيل المثال، بقول "اختر عشوائيًا" $n<m$ أو بافتراض أن مجموعة من $m$ عنصرًا تحتوي على عنصر.

التكافؤ مع الاستقراء العادي

الاستقراء الكامل مكافئ للاستقراء الرياضي العادي كما هو موضح أعلاه، بمعنى أنه يمكن تحويل برهان باستخدام إحدى الطريقتين إلى برهان باستخدام الأخرى. لنفترض وجود برهان لـ $P(n)$ بالاستقراء الكامل. بعد ذلك، يمكن تحويل هذا البرهان إلى برهان استقراء عادي بافتراض فرضية استقرائية أقوى. ليكن $Q(n)$ كن البيان " $P(m)$ ينطبق على الجميع $m$ بحيث $0\leq m\leq n$ "—يصبح هذا الفرض الاستقرائي للاستقراء العادي. يمكننا حينها أن نُبين $Q(0)$ و $Q(n+1)$ ل $n\in \mathbb {N}$ بافتراض فقط $Q(n)$ وأظهر ذلك $Q(n)$ يشير إلى $P(n)$ [ ²²^]

أما إذا، من ناحية أخرى، $P(n)$ إذا تم إثبات ذلك بالاستقراء العادي، فإن البرهان سيكون في الواقع برهاناً بالاستقراء الكامل: $P(0)$ وقد تم إثبات ذلك في الحالة الأساسية، دون استخدام أي افتراضات، و $P(n+1)$ يتم إثبات ذلك في خطوة الاستقراء، حيث يمكن للمرء أن يفترض جميع الحالات السابقة ولكنه يحتاج فقط إلى استخدام الحالة $P(n)$ .

مثال: أعداد فيبوناتشي

يُعد الاستقراء الكامل مفيدًا للغاية عندما يتطلب الأمر عدة أمثلة على فرضية الاستقراء لكل خطوة من خطوات الاستقراء. على سبيل المثال، يمكن استخدام الاستقراء الكامل لإثبات أن $F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}$ أين $F_{n}$ هو العدد $النوني$ في متتالية فيبوناتشي ، و ${\textstyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}$ ( النسبة الذهبية ) و ${\textstyle \psi ={\frac {1}{2}}(1-{\sqrt {5}})}$ هي جذور متعددة الحدود $x^{2}-x-1$ باستخدام حقيقة أن $F_{n+2}=F_{n+1}+F_{n}$ لكل $n\in \mathbb {N}$ يمكن التحقق من الهوية المذكورة أعلاه عن طريق الحساب المباشر لـ ${\textstyle F_{n+2}}$ إذا افترضنا أن هذا ينطبق بالفعل على كليهما ${\textstyle F_{n+1}}$ و ${\textstyle F_{n}}$ لإكمال البرهان، يجب التحقق من الهوية في الحالتين الأساسيتين: $n=0$ و ${\textstyle n=1}$ .

مثال: التحليل إلى العوامل الأولية

يستخدم برهان آخر بالاستقراء الكامل فرضية أن العبارة صحيحة لجميع القيم الأصغر $n$ بمزيد من التفصيل، لننظر في العبارة التي تنص على أن "كل عدد طبيعي أكبر من 1 هو حاصل ضرب عدد أولي واحد أو أكثر "، وهو ما يمثل " الوجود " في النظرية الأساسية للحساب . ولإثبات خطوة الاستقراء، فإن فرضية الاستقراء هي أنه بالنسبة لعدد معطى $m>1$ ينطبق هذا البيان على جميع الأحجام الأصغر $n>1$ . لو $m$ إذا كان عدداً أولياً فهو بالتأكيد ناتج ضرب أعداد أولية، وإذا لم يكن كذلك فهو، بحكم التعريف، ناتج ضرب: $m=n_{1}n_{2}$ حيث لا يساوي أي من العاملين 1؛ وبالتالي لا يساوي أي منهما 1. $m$ وبالتالي، كلاهما أكبر من 1 وأصغر من $m$ تنطبق فرضية الاستقراء الآن على $n_{1}$ و $n_{2}$ إذن، كل واحد منها هو ناتج ضرب أعداد أولية. $m$ هو ناتج ضرب الأعداد الأولية، وبالتالي فهو بالتبعية ناتج ضرب الأعداد الأولية نفسه.

مثال: إعادة النظر في المبالغ الدولارية

سنحاول إثبات المثال نفسه المذكور أعلاه ، ولكن هذه المرة باستخدام الاستقراء القوي . وتبقى العبارة كما هي: $S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b$

ومع ذلك، ستكون هناك اختلافات طفيفة في بنية وافتراضات البرهان، بدءًا من الحالة الأساسية الموسعة.

دليل.

الحالة الأساسية: أثبت أن $S(k)$ يحمل لـ $k=12,13,14,15$ . ${\begin{aligned}4\cdot 3+5\cdot 0=12\\4\cdot 2+5\cdot 1=13\\4\cdot 1+5\cdot 2=14\\4\cdot 0+5\cdot 3=15\end{aligned}}$

الحالة الأساسية صحيحة.

خطوة الاستقراء: بالنظر إلى بعض $j>15$ ، يفترض $S(m)$ ينطبق على الجميع $m$ مع $12\leq m<j$ أثبت ذلك $S(j)$ يحجز.

اختيار $m=j-4$ وملاحظة ذلك $15<j\implies 12\leq j-4<j$ يُظهر ذلك أن $S(j-4)$ يثبت ذلك، وفقًا لفرضية الاستقراء. أي أن المجموع $j-4$ يمكن تشكيلها من خلال مزيج من $4$ و $5$ عملات الدولار. ثم، ببساطة إضافة $4$ إضافة عملة الدولار إلى هذا المزيج ينتج عنه المجموع $j$ . إنه، $S(j)$ يثبت. ^{[ 23 ]} وهو المطلوب إثباته

الاستقراء الأمامي والخلفي

أحيانًا، يكون من الأنسب الاستدلال العكسي، مما يثبت صحة العبارة لـ $n-1$ ، بالنظر إلى صلاحيتها لـ $n$ مع ذلك، لا يكفي إثبات صحة العبارة لعدد واحد لتحديد الحالة الأساسية؛ بل يلزم إثباتها لمجموعة جزئية لانهائية من الأعداد الطبيعية. على سبيل المثال، استخدم أوغستين لويس كوشي الاستقراء الأمامي (المنتظم) أولًا لإثبات متباينة الوسطين الحسابي والهندسي لجميع قوى العدد 2 ، ثم استخدم الاستقراء العكسي لإثباتها لجميع الأعداد الطبيعية. ^{[ 24 ]}^{[ 25 ]}

مثال على خطأ في خطوة الاستقراء

يجب إثبات خطوة الاستقراء لجميع قيم $n$ . ولتوضيح ذلك، اقترح جويل إي. كوهين الحجة التالية، والتي تزعم إثبات أن جميع الخيول من نفس اللون عن طريق الاستقراء الرياضي : ^{[ 26 ]}

الحالة الأساسية: في مجموعة تتكون من حصان واحد فقط ، يوجد لون واحد فقط.

خطوة الاستقراء: افترض كفرضية استقراء أنه ضمن أي مجموعة من $n$ الخيول، لا يوجد سوى لون واحد. انظر الآن إلى أي مجموعة من $n+1$ الخيول. رتبها حسب العدد التالي: $1,2,3,\dotsc ,n,n+1$ ضع في اعتبارك المجموعات ${\textstyle \left\{1,2,3,\dotsc ,n\right\}}$ و ${\textstyle \left\{2,3,4,\dotsc ,n+1\right\}}$ كل منها عبارة عن مجموعة من فقط $n$ لذا، يوجد لون واحد فقط ضمن كل مجموعة من الخيول. لكن المجموعتين تتداخلان، لذا يجب أن يكون هناك لون واحد فقط بين جميعها. $n+1$ خيل.

الحالة الأساسية $n=1$ الأمر بديهي، وخطوة الاستقراء صحيحة في جميع الحالات $n>1$ ومع ذلك، فإن الحجة المستخدمة في خطوة الاستقراء غير صحيحة بالنسبة لـ $n+1=2$ لأن العبارة القائلة بأن "المجموعتين تتداخلان" خاطئة بالنسبة لـ ${\textstyle \left\{1\right\}}$ و ${\textstyle \left\{2\right\}}$ .

الإضفاء الطابع الرسمي

في منطق الرتبة الثانية ، يمكن كتابة " بديهية الاستقراء" على النحو التالي: $\forall P\,{\Bigl (}P(0)\land \forall k{\bigl (}P(k)\to P(k+1){\bigr )}\to \forall n\,{\bigl (}P(n){\bigr )}{\Bigr )},$ حيث $P (\cdot)$ هو متغير للمسندات التي تتضمن عددًا طبيعيًا واحدًا و $k$ و $n$ هما متغيرات للأعداد الطبيعية .

بمعنى آخر، فإن الحالة الأساسية $P (0)$ وخطوة الاستقراء (أي أن فرضية الاستقراء $P (k)$ تستلزم $P (k + 1)$ ) تستلزمان معًا أن $P (n)$ صحيحة لأي عدد طبيعي $n$ . وتؤكد بديهية الاستقراء صحة استنتاج أن $P (n)$ صحيحة لأي عدد طبيعي $n$ من الحالة الأساسية وخطوة الاستقراء.

يُغطي المُكمِّم الأول في البديهية المسندات بدلاً من الأعداد الفردية. هذا مُكمِّم من الدرجة الثانية، مما يعني أن هذه البديهية مُصاغة في منطق الدرجة الثانية . يتطلب وضع بديهيات الاستقراء الحسابي في منطق الدرجة الأولى مخطط بديهيات يحتوي على بديهية منفصلة لكل مسند مُحتمل. تتضمن مقالة بديهيات بيانو مزيدًا من النقاش حول هذه المسألة.

صاغ بيانو أول بديهية الاستقراء البنيوي للأعداد الطبيعية، واستخدمها لتحديد الأعداد الطبيعية إلى جانب البديهيات الأربع الأخرى التالية:

الصفر عدد طبيعي.
الدالة اللاحقة $s$ لكل عدد طبيعي تعطي عددًا طبيعيًا $(s (x) = x + 1)$ .
الدالة اللاحقة أحادية .
0 ليس ضمن نطاق s $.$

في نظرية المجموعات ZFC من الدرجة الأولى ، لا يُسمح بالتكميم على المسندات، ولكن لا يزال بإمكان المرء التعبير عن الاستقراء عن طريق التكميم على المجموعات: $\forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}$ $يمكن قراءة A$ على أنها مجموعة تمثل قضية، وتحتوي على أعداد طبيعية، تتحقق عندها تلك القضية. هذه ليست بديهية، بل نظرية، نظرًا لأن الأعداد الطبيعية تُعرَّف في لغة نظرية مجموعات ZFC بواسطة بديهيات، على غرار بديهيات بيانو. انظر بناء الأعداد الطبيعية باستخدام بديهية اللانهاية ومخطط بديهيات التحديد .

الاستقراء المتسامي

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

عند تطبيق الاستقراء المتسامي على مجموعة ذات أساس متين، يمكن صياغته كخطوة واحدة. لإثبات صحة العبارة $P (n)$ لكل عدد ترتيبي:

أثبت، لكل عدد ترتيبي $n$ ، أنه إذا تحققت $P (m)$ لجميع $m < n$ ، فإن $P (n)$ تتحقق أيضًا.

يُطلق على هذا النوع من الاستقراء، عند تطبيقه على مجموعة من الأعداد الترتيبية (التي تُشكّل فئة مُرتبة ترتيبًا جيدًا وبالتالي ذات أساس متين )، اسم الاستقراء المتسامي . وهو أسلوب إثبات مهم في نظرية المجموعات والطوبولوجيا وغيرها من المجالات.

تُميّز البراهين بالاستقراء المتسامي عادةً ثلاث حالات:

عندما يكون $n$ عنصرًا أصغر، أي لا يوجد عنصر أصغر من $n$ ؛
عندما يكون لـ $n$ سلف مباشر، أي أن مجموعة العناصر الأصغر من $n$ تحتوي على أكبر عنصر؛
عندما لا يكون لـ $n سلف مباشر، أي أن$ $n$ هو ما يسمى بالعدد الترتيبي الحدي .

بالمعنى الدقيق، ليس من الضروري في الاستقراء المتسامي إثبات حالة أساسية، لأنها حالة خاصة فارغة من القضية القائلة بأنه إذا كانت $P$ صحيحة لجميع $قيم n < m$ ، فإن $P$ صحيحة لـ $m$ . وهي صحيحة بشكل فارغ تحديدًا لعدم وجود قيم $n < m$ يمكن أن تُستخدم كأمثلة مضادة. لذا، فإن الحالات الخاصة هي حالات خاصة من الحالة العامة.

العلاقة بمبدأ الترتيب الجيد

يُصاغ مبدأ الاستقراء الرياضي عادةً كمسلمة من مسلمات الأعداد الطبيعية؛ انظر مسلمات بيانو . وهو أقوى بكثير من مبدأ الترتيب الجيد في سياق مسلمات بيانو الأخرى. لنفترض ما يلي:

بديهية التثليث : لأي عددين طبيعيين $n$ و $m$ ، يكون $n$ أصغر من أو يساوي $m$ إذا وفقط إذا كان $m$ ليس أصغر من $n$ .
لأي عدد طبيعي $n$ ، يكون $n + 1$ أكبر من n .
بالنسبة لأي عدد طبيعي $n$ ، لا يوجد عدد طبيعي بين n و $n + 1$ .
لا يوجد عدد طبيعي أقل من الصفر.

يمكن إثبات أن الاستقراء، في ضوء البديهيات المذكورة أعلاه، يستلزم مبدأ الترتيب الجيد. ويستخدم البرهان التالي الاستقراء الكامل والبديهيتين الأولى والرابعة.

البرهان. لنفترض وجود مجموعة غير فارغة ، $S$ ، من الأعداد الطبيعية ليس لها أصغر عنصر. ولتكن $P (n)$ هي العبارة التي تنص على أن $n$ ليس في $S.$ إذن $P (0)$ صحيحة، لأنه لو كانت خاطئة لكان 0 أصغر عنصر في $S.$ علاوة على ذلك، ليكن $n$ عددًا طبيعيًا، ولنفترض أن $P (m)$ صحيحة لجميع الأعداد الطبيعية $m$ الأقل من $n + 1.$ إذن إذا كانت $P (n + 1)$ خاطئة، فإن $n + 1$ ينتمي إلى $S$ ، وبالتالي فهو أصغر عنصر في $S$ ، وهذا تناقض. إذن $P (n + 1)$ صحيحة. لذلك، وفقًا لمبدأ الاستقراء الكامل، فإن $P (n)$ صحيحة لجميع الأعداد الطبيعية $n$ ؛ وبالتالي فإن $S$ فارغة، وهذا تناقض. انتهى البرهان.

" خط الأعداد " للمجموعة

{(0, n): n \in N} \cup {(1, n): n \in N}

. تشير الأرقام إلى المكون الثاني للأزواج؛ ويمكن الحصول على المكون الأول من اللون أو الموقع.

من ناحية أخرى، المجموعة $\{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}$ كما هو موضح في الصورة، فإنّ الترتيب المعجمي [27]: 35lf مُرتب ترتيبًا جيدًا . علاوة ^{على ذلك ،}^{باستثناء بديهية} الاستقراء، فإنه يُحقق جميع بديهيات بيانو، حيث يُفسَّر ثابت بيانو 0 على أنه الزوج (0، 0)، وتُعرَّف دالة بيانو اللاحقة على الأزواج بواسطة $succ($ $x$ $,$ $n$ $) = ($ $x$ $,$ $n$ $+$ $1)$ لجميع $x\in \{0,1\}$ و $n\in \mathbb {N}$ كمثال على انتهاك بديهية الاستقراء، عرّف المسند $P (x, n)$ على أنه $(x, n) = (0, 0)$ أو $(x, n) = succ(y, m)$ لبعض $y\in \{0,1\}$ و $m\in \mathbb {N}$ إذن، تكون الحالة الأساسية $P (0, 0)$ صحيحة بشكل بديهي، وكذلك خطوة الاستقراء: إذا كانت $P (x, n)$ ، فإن $P (succ(x, n))$ . مع ذلك، فإن $P$ ليست صحيحة لجميع الأزواج في المجموعة، لأن $P (1, 0)$ خاطئة.

تُقدّم بديهيات بيانو، مع مبدأ الاستقراء، نموذجًا فريدًا للأعداد الطبيعية. ويُتيح استبدال مبدأ الاستقراء بمبدأ الترتيب الجيد نماذج أكثر تعقيدًا تُحقق جميع البديهيات. ^{[ 27 ]}

ورد خطأً في العديد من الكتب ^{[ 27 ]} والمصادر أن مبدأ الترتيب الجيد يُكافئ بديهية الاستقراء. في سياق بديهيات بيانو الأخرى، لا ينطبق هذا، ولكنهما متكافئان في سياق بديهيات أخرى؛ ^{[ 27 ]} تحديدًا، يستلزم مبدأ الترتيب الجيد بديهية الاستقراء في سياق البديهيتين الأوليين المذكورتين أعلاه.

كل عدد طبيعي إما أن يكون 0 أو $n + 1$ لعدد طبيعي $ما n$ .

من الأخطاء الشائعة في العديد من البراهين الخاطئة افتراض أن $n - 1$ هو عدد طبيعي فريد ومحدد جيدًا، وهي خاصية لا تستلزمها بديهيات بيانو الأخرى. ^{[ 27 ]}

انظر أيضاً

ملحوظات

↑ مات ديفوس، الاستقراء الرياضي ، جامعة سيمون فريزر
↑ جيراردو كون دياز، الاستقراء الرياضي، مؤرشف في 2 مايو 2013 على موقع Wayback Machine ، جامعة هارفارد
↑ أندرسون، روبرت ب. (1979). إثبات صحة البرامج . نيويورك: جون وايلي وأولاده. ص 1. ISBN 978-0471033950.
↑ سوبر، بيتر. "الاستقراء الرياضي" . كلية إيرلهام. مؤرشف من الأصل في 24 مايو 2011. تم الاطلاع عليه في 26 مارس 2011 .
↑ "أصول إقليدس، الكتاب السابع، التعريفان 1 و2" . webspace.ship.edu . تم الاطلاع عليه بتاريخ 23 مايو 2026 .
↑ أسيربي، فابيو (1 يناير 2000). "أفلاطون: بارمنيدس 149أ7-ج3. برهان بالاستقراء الكامل؟" . أرشيف تاريخ العلوم الدقيقة 55 (2000)، 57-76 .
↑ سريامان، بهارات، محرر (2024)، دليل تاريخ وفلسفة الممارسة الرياضية. المجلد 4، مرجع سبرينغر الطبيعي، تشام: سبرينغر، ص 985، ISBN 978-3-031-40845-8، بقراءة المصادر بدقة، لدينا بعض الحجج الجديدة التي تُظهر أن الفيثاغوريين كان لديهم بالفعل برهان استقرائي، ولكن بدون مبدأ الاستقراء الرياضي.
↑ راشد 1994 ، ص 62-84.
↑ المعرفة الرياضية والتفاعل بين الممارسات "أُعطي أقدم برهان ضمني عن طريق الاستقراء الرياضي حوالي عام 1000 في عمل للرياضي الفارسي الكرجي"
↑ «نظرية ذات الحدين» . mathcenter.oxford.emory.edu . تاريخ الاطلاع: 2 ديسمبر 2024. مع ذلك، لم يكن أول من درسها. يُنسب الفضل حاليًا في اكتشافها إلى عالم الرياضيات والمهندس الفارسي الكرجي، الذي عاش بين عامي 935 و1029. ( معلومة جانبية مثيرة للاهتمام: قدم الكرجي أيضًا فكرة الاستدلال بالاستقراء الرياضي ) .
↑ كاتز (1998)، ص 255
1 2 كاجوري (1918) ، ص 197: «إن عملية الاستدلال المسماة "الاستقراء الرياضي" لها عدة أصول مستقلة. وقد تم تتبعها إلى السويسري جاكوب (جيمس) برنولي، والفرنسيين بيير باسكال وبولس فيرما، والإيطالي فريدريك ماوروليكوس. [...] من خلال قراءة ما بين السطور، يمكن للمرء أن يجد آثارًا للاستقراء الرياضي في وقت أبكر، في كتابات الهنود واليونانيين، كما هو الحال، على سبيل المثال، في "الطريقة الدورية" لبهاسكارا، وفي برهان إقليدس على أن عدد الأعداد الأولية لا نهائي.»
↑ راشد 1994 ، ص 62.
↑ سيمونسون 2000 .
↑ رابينوفيتش 1970 .
↑ «قد يُطلب أحيانًا إثبات نظرية تكون صحيحة كلما كانت الكمية n التي تتضمنها عددًا صحيحًا، وعادةً ما تكون طريقة الإثبات على النحو التالي: أولًا، يُثبت صحة النظرية عندما n = 1. ثانيًا، يُثبت أنه إذا كانت النظرية صحيحة عندما يكون n عددًا صحيحًا مُعطى ، فستكون صحيحة إذا كان n هو العددالصحيح الأكبر منه. ومن ثم، فإن النظرية صحيحة بشكل عام. ... يمكن تسمية هذا النوع من الحجج بالاستدلال المستمر » (بول، حوالي 1849، رسالة تمهيدية في المنطق، غير رياضي ، ص 40-41، أعيد طبعه في: غراتان-غينيس، إيفور وبورنيه، جيرار (1997)، جورج بول: مخطوطات مختارة في المنطق وفلسفته ، دار بيركهاوزر للنشر، برلين، ISBN). 3-7643-5456-9)
↑ بيرس 1881 .
↑ شيلدز 1997 .
↑ تيد سوندستروم، الاستدلال الرياضي ، ص 190، بيرسون، 2006، رقم ISBN 978-0131877184
↑ سموليان، ريموند (2014). دليل المبتدئين في المنطق الرياضي . دوفر. ص 41. ISBN 978-0486492377.
↑ بوس، صموئيل (1986). الحساب المحدود . نابولي: بيبليوبوليس.
↑ "برهان: الاستقراء القوي مكافئ للاستقراء الضعيف" . جامعة كورنيل . تم الاطلاع عليه بتاريخ 4 مايو 2023 .
↑ شفيعي، نيلوفر. "الاستقراء القوي والترتيب الجيد" (ملف PDF) . جامعة يورك . تم الاطلاع عليه بتاريخ 28 مايو 2023 .
↑ "الاستقراء الأمامي والخلفي | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 23 أكتوبر 2019 .
↑ كوشي، أوغسطين لويس (1821). دروس التحليل في المدرسة الملكية للفنون التطبيقية، الجزء الأول، التحليل الجبري، مؤرشف في 14 أكتوبر 2017 في أرشيف الإنترنت في باريس. يمكن الاطلاع على برهان متباينة الوسطين الحسابي والهندسي في الصفحات 457 وما بعدها.
↑ كوهين، جويل إي. (1961). "حول طبيعة البرهان الرياضي". أوبوس .. أعيد طبعه في كتاب "A Random Walk in Science " (تحرير آر إل ويبر)، دار نشر كرين، روساك وشركاه، 1973.
1 2 3 4 5 أومان، لارس-دانيال (6 مايو 2019). "هل الاستقراء والترتيب الجيد متكافئان؟" . مجلة الرياضيات الذكية . 41 (3): 33-40 . doi : 10.1007/s00283-019-09898-4 .

مراجع

مقدمة

فرانكلين، ج .؛ داود، أ. (2011). البرهان في الرياضيات: مقدمة . سيدني: كيو بوكس. ISBN 978-0-646-54509-7.(الفصل 8.)
"الاستقراء الرياضي" . موسوعة الرياضيات . دار نشر EMS . 2001 [1994].
هيرمس، هانز (1973). مقدمة في المنطق الرياضي . هوخشولتكست. لندن: سبرينغر. ISBN 978-3540058199ISSN 1431-4657 . MR 0345788 .
كنوت، دونالد إي. (1997). فن برمجة الحاسوب، المجلد 1: الخوارزميات الأساسية ( الطبعة الثالثة). أديسون-ويسلي. ISBN 978-0-201-89683-1.(القسم 1.2.1: الاستقراء الرياضي، الصفحات 11-21.)
كولموغوروف، أندريه ن .؛ فومين، سيرجي ف. (1975). مدخل إلى التحليل الحقيقي . ترجمة وتحرير: سيلفرمان، ر. أ. نيويورك: دوفر. ISBN 978-0-486-61226-3.(القسم 3.8: الاستقراء المتغاير، الصفحات 28-29.)

تاريخ

أتشيربي، فابيو (أغسطس 2000). " أفلاطون: بارمنيدس 149أ7-ج3. برهان بالاستقراء الكامل؟" . أرشيف تاريخ العلوم الدقيقة . 55 (1): 57-76 . doi : 10.1007/s004070000020 . JSTOR 41134098. S2CID 123045154 .
بوسّي، دبليو إتش (1917). "أصل الاستقراء الرياضي". المجلة الرياضية الأمريكية الشهرية . 24 (5): 199-207 . doi : 10.2307/2974308 . JSTOR 2974308 .
كاجوري، فلوريان (1918). "أصل تسمية "الاستقراء الرياضي"". المجلة الرياضية الأمريكية الشهرية . 25 (5): 197–201 . doi : 10.2307/2972638 . JSTOR 2972638 .
فاولر، د. (1994). "هل استخدم الإغريق الاستقراء الرياضي؟ وهل استخدموه فعلاً؟". فيزيس . 31 : 253-265 .
فرويدينثال، هانز (1953). "Zur Geschichte der vollständigen Induction". المحفوظات الدولية لتاريخ العلوم . 6 : 17 - 37.
كاتز، فيكتور ج. (1998). تاريخ الرياضيات: مقدمة . أديسون-ويسلي . ISBN 0-321-01618-1.
بيرس، تشارلز ساندرز (1881). " في منطق الأعداد" . المجلة الأمريكية للرياضيات . 4 ( 1-4 ): 85-95 . doi : 10.2307/2369151 . JSTOR 2369151. MR 1507856 . أُعيد طبعه (CP 3.252–288)، (W 4:299–309)
رابينوفيتش، ناحوم ل. ( 1970). "الحاخام ليفي بن غيرشون وأصول الاستقراء الرياضي". أرشيف تاريخ العلوم الدقيقة . 6 (3): 237-248 . doi : 10.1007/BF00327237 . MR 1554128. S2CID 119948133 .
راشد، رشدي (1972). "الاستقراء الرياضي: الكرجي، السماول". أرشيف تاريخ العلوم الدقيقة ( بالفرنسية). 9 (1): 1-21 . doi : 10.1007/BF00348537 . MR 1554160. S2CID 124040444 .
راشد، ر. (1994). "الاستقراء الرياضي: الكرجي والسموال". تطور الرياضيات العربية: بين الحساب والجبر . دراسات بوسطن في فلسفة العلوم. المجلد 156. سبرينغر للعلوم والأعمال. ISBN 9780792325659.
شيلدز، بول (1997). "مسلمات بيرس في الحساب". في: هاوزر، ناثان؛ روبرتس، دون د.؛ إيفرا، جيمس فان (محررون). دراسات في منطق تشارلز س. بيرس . مطبعة جامعة إنديانا. ص 43-52 . ISBN 0-253-33020-3MR 1720827 .
سيمونسون، تشارلز ج. (شتاء 2000). "رياضيات ليفي بن غيرشون، الرالباغ" (ملف PDF) . بيكهول دراخيكا ديهو . 10. مطبعة جامعة بار إيلان: 5-21 . مؤرشف من الأصل (ملف PDF) في 11 أكتوبر 2017. تم الاطلاع عليه في 29 ديسمبر 2019 .
أونغورو، س. (1991). "الرياضيات اليونانية والاستقراء الرياضي". فيزيس . 28 : 273-289 .
أونغورو، س. (1994). “الصيد بعد الحث”. الفيزياء . 31 : 267 – 272.
فاكا، ج. (1909). "موروليكوس، أول من اكتشف مبدأ الاستقراء الرياضي" . نشرة الجمعية الرياضية الأمريكية . 16 (2): 70-73 . doi : 10.1090/S0002-9904-1909-01860-9 . MR 1558845 .
يادغاري، محمد (1978) . "استخدام الاستقراء الرياضي عند أبي كامل شجاع بن أسلم (850-930)". إيزيس . 69 (2): 259-262 . doi : 10.1086/352009 . JSTOR 230435. S2CID 144112534 .

[1] مات ديفوس، الاستقراء الرياضي ، جامعة سيمون فريزر

[2] جيراردو كون دياز، الاستقراء الرياضي، مؤرشف في 2 مايو 2013 على موقع Wayback Machine ، جامعة هارفارد

[3] أندرسون، روبرت ب. (1979). إثبات صحة البرامج . نيويورك: جون وايلي وأولاده. ص 1. ISBN 978-0471033950.

[4] سوبر، بيتر. "الاستقراء الرياضي" . كلية إيرلهام. مؤرشف من الأصل في 24 مايو 2011. تم الاطلاع عليه في 26 مارس 2011 .

[5] "أصول إقليدس، الكتاب السابع، التعريفان 1 و2" . webspace.ship.edu . تم الاطلاع عليه بتاريخ 23 مايو 2026 .

[6] أسيربي، فابيو (1 يناير 2000). "أفلاطون: بارمنيدس 149أ7-ج3. برهان بالاستقراء الكامل؟" . أرشيف تاريخ العلوم الدقيقة 55 (2000)، 57-76 .

[7] سريامان، بهارات، محرر (2024)، دليل تاريخ وفلسفة الممارسة الرياضية. المجلد 4، مرجع سبرينغر الطبيعي، تشام: سبرينغر، ص 985، ISBN 978-3-031-40845-8، بقراءة المصادر بدقة، لدينا بعض الحجج الجديدة التي تُظهر أن الفيثاغوريين كان لديهم بالفعل برهان استقرائي، ولكن بدون مبدأ الاستقراء الرياضي.

[FOOTNOTERashed199462–84-8] راشد 1994 ، ص 62-84.

[9] المعرفة الرياضية والتفاعل بين الممارسات "أُعطي أقدم برهان ضمني عن طريق الاستقراء الرياضي حوالي عام 1000 في عمل للرياضي الفارسي الكرجي"

[10] «نظرية ذات الحدين» . mathcenter.oxford.emory.edu . تاريخ الاطلاع: 2 ديسمبر 2024. مع ذلك، لم يكن أول من درسها. يُنسب الفضل حاليًا في اكتشافها إلى عالم الرياضيات والمهندس الفارسي الكرجي، الذي عاش بين عامي 935 و1029. ( معلومة جانبية مثيرة للاهتمام: قدم الكرجي أيضًا فكرة الاستدلال بالاستقراء الرياضي ) .

[11] كاتز (1998)، ص 255

[Induction_Bussey-12] 1 2 كاجوري (1918) ، ص 197: «إن عملية الاستدلال المسماة "الاستقراء الرياضي" لها عدة أصول مستقلة. وقد تم تتبعها إلى السويسري جاكوب (جيمس) برنولي، والفرنسيين بيير باسكال وبولس فيرما، والإيطالي فريدريك ماوروليكوس. [...] من خلال قراءة ما بين السطور، يمكن للمرء أن يجد آثارًا للاستقراء الرياضي في وقت أبكر، في كتابات الهنود واليونانيين، كما هو الحال، على سبيل المثال، في "الطريقة الدورية" لبهاسكارا، وفي برهان إقليدس على أن عدد الأعداد الأولية لا نهائي.»

[FOOTNOTERashed199462-13] راشد 1994 ، ص 62.

[FOOTNOTESimonson2000-14] سيمونسون 2000 .

[FOOTNOTERabinovitch1970-15] رابينوفيتش 1970 .

[16] «قد يُطلب أحيانًا إثبات نظرية تكون صحيحة كلما كانت الكمية n التي تتضمنها عددًا صحيحًا، وعادةً ما تكون طريقة الإثبات على النحو التالي: أولًا، يُثبت صحة النظرية عندما n = 1. ثانيًا، يُثبت أنه إذا كانت النظرية صحيحة عندما يكون n عددًا صحيحًا مُعطى ، فستكون صحيحة إذا كان n هو العددالصحيح الأكبر منه. ومن ثم، فإن النظرية صحيحة بشكل عام. ... يمكن تسمية هذا النوع من الحجج بالاستدلال المستمر » (بول، حوالي 1849، رسالة تمهيدية في المنطق، غير رياضي ، ص 40-41، أعيد طبعه في: غراتان-غينيس، إيفور وبورنيه، جيرار (1997)، جورج بول: مخطوطات مختارة في المنطق وفلسفته ، دار بيركهاوزر للنشر، برلين، ISBN). 3-7643-5456-9)

[FOOTNOTEPeirce1881-17] بيرس 1881 .

[FOOTNOTEShields1997-18] شيلدز 1997 .

[19] تيد سوندستروم، الاستدلال الرياضي ، ص 190، بيرسون، 2006، رقم ISBN 978-0131877184

[20] سموليان، ريموند (2014). دليل المبتدئين في المنطق الرياضي . دوفر. ص 41. ISBN 978-0486492377.

[Buss:BA-21] بوس، صموئيل (1986). الحساب المحدود . نابولي: بيبليوبوليس.

[22] "برهان: الاستقراء القوي مكافئ للاستقراء الضعيف" . جامعة كورنيل . تم الاطلاع عليه بتاريخ 4 مايو 2023 .

[yorku-23] شفيعي، نيلوفر. "الاستقراء القوي والترتيب الجيد" (ملف PDF) . جامعة يورك . تم الاطلاع عليه بتاريخ 28 مايو 2023 .

[24] "الاستقراء الأمامي والخلفي | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 23 أكتوبر 2019 .

[25] كوشي، أوغسطين لويس (1821). دروس التحليل في المدرسة الملكية للفنون التطبيقية، الجزء الأول، التحليل الجبري، مؤرشف في 14 أكتوبر 2017 في أرشيف الإنترنت في باريس. يمكن الاطلاع على برهان متباينة الوسطين الحسابي والهندسي في الصفحات 457 وما بعدها.

[26] كوهين، جويل إي. (1961). "حول طبيعة البرهان الرياضي". أوبوس .. أعيد طبعه في كتاب "A Random Walk in Science " (تحرير آر إل ويبر)، دار نشر كرين، روساك وشركاه، 1973.

[Ohman2019-27] 1 2 3 4 5 أومان، لارس-دانيال (6 مايو 2019). "هل الاستقراء والترتيب الجيد متكافئان؟" . مجلة الرياضيات الذكية . 41 (3): 33-40 . doi : 10.1007/s00283-019-09898-4 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[ 19 ]

[ 20 ]

22

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

على ذلك ،

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗