الاستقراء الرياضي هو طريقة إثبات رياضية تُستخدم عادةً لإثبات أن جملة معينة صحيحة لجميع الأعداد الطبيعية (الأعداد الصحيحة غير السالبة)، يتم ذلك عن طريق إثبات أن العبارة الأولى في التسلسل اللانهائي من العبارات صحيحة، ثم إثبات أنه إذا كانت أي جملة واحدة في التسلسل اللانهائي من العبارات صحيحة، فإن الجملة التالية تكون كذلك. [1]

مفهوم الاستقراء الرياضي

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

مبدأ الاستقراء الرياضي

تسمى فئة الأعداد الصحيحة بالوراثة إذا كان أي عدد صحيح x ينتمي إلى الفئة، فإن خليفة x (أي العدد الصحيح x + 1) ينتمي أيضًا إلى الفئة.

مبدأ

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

هو: إذا كان العدد الصحيح 0 ينتمي إلى الفئة F وكان F وراثيًا، فكل عدد صحيح غير سالب ينتمي إلى F، بدلاً من ذلك، إذا كان العدد الصحيح 1 ينتمي إلى الفئة F و F هو وراثي، فإن كل عدد صحيح موجب ينتمي إلى F، يتم ذكر المبدأ في بعض الأحيان في شكل واحد، وأحيانًا في الآخر، نظرًا لأنه من السهل إثبات أي شكل من أشكال المبدأ كنتيجة للآخر، فليس من الضروري التمييز بين الاثنين.

غالبًا ما يتم ذكر المبدأ في شكل مكثف: تسمى خاصية الأعداد الصحيحة بالوراثة، إذا كان لأي عدد صحيح x خاصية، فإن خلفها له الخاصية. إذا كان للعدد الصحيح 1 خاصية معينة وكانت هذه الخاصية وراثية، فإن كل عدد صحيح موجب له الخاصية.

البرهان باستعمال مبدأ الاستقراء الرياضي

مثال على تطبيق الاستقراء الرياضي في أبسط الحالات هو الدليل على أن مجموع أول n من الأعداد الصحيحة الموجبة الفردية هو n
²
أي أن

(1.)

1 + 3 + 5 +⋯+ (2n − 1) = n
²

لكل عدد صحيح موجب n، لنفترض أن F هي فئة الأعداد الصحيحة التي تحمل المعادلة

(1.)

لها؛ إذن، العدد الصحيح 1 ينتمي إلى F، لأن 1 = 12، إذا كان أي عدد صحيح x ينتمي إلى F، إذن

(2.)

1 + 3 + 5 +⋯+ (2x − 1) = x
²

العدد الصحيح الفردي التالي بعد 2x − 1 هو 2x + 1، وعندما يضاف إلى كلا طرفي المعادلة

(2.)

، تكون النتيجة هي

(3.)

1 + 3 + 5 +⋯+ (2x + 1) = x
²
+ 2x + 1 = (x + 1)
²

تسمى المعادلة

(2.)

فرضية الاستقراء وتنص على أن المعادلة

(1.)

تصمد عندما تكون n هي x ، بينما تنص المعادلة

(3.)

على أن المعادلة

(1.)

تصمد عندما تكون n هي x + 1، نظرًا لأن المعادلة

(3.)

، كنتيجة للمعادلة

(2.)

، فقد ثبت أنه عندما ينتمي x إلى F، فإن خليفة x ينتمي إلى F، ومن ثم وفقًا لمبدأ الاستقراء الرياضي، فإن جميع الأعداد الصحيحة الإيجابية تنتمي إلى F.

لإثبات أن علاقة ثنائية معينة F تحمل بين جميع الأعداد الصحيحة الموجبة، يكفي أن نظهر أولاً أن العلاقة F بين 1 و 1؛ ثانيًا، عندما تحمل F بين x و y، فإنها تثبت بين x و y + 1 ؛ وثالثًا، عندما تحمل F بين x وعدد صحيح موجب معين z (والذي قد يكون ثابتًا أو يعتمد على x)، فإنه يثبت بين x + 1 و 1. [2]

خطوات الاستنتاج الرياضي

الخطوة الأولى: (الأساس) أظهر أن P (n₀) صحيحة.
الخطوة الثانية: (الفرضية الاستقرائية)، اكتب الفرضية الاستقرائية: لنفترض أن k عددًا صحيحًا بحيث يكون k ≥ n₀ و P (k) صحيحين.
الخطوة الثالثة: (خطوة استقرائية). بيّن أن P (k + 1) صحيحة.

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

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

كما لو كانت العبارة صحيحة بالنسبة لـ P (k) ، فسيكون ذلك صحيحًا بالنسبة ل P (k + 1) ، لذلك إذا كان هذا صحيحًا بالنسبة لـ P (1) فيمكن إثبات ذلك لـ P (1 + 1) أو P (2 ) بالمثل لـ P (3) و P (4) وهكذا حتى ن أعداد طبيعية.

الإثبات عن طريق الاستقراء الرياضي

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

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

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

افتراض الحث العكسي

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

الحث القوي يشبه الحث الضعيف. لكن بالنسبة للحث القوي في الخطوة الاستقرائية، نفترض أن كل P (1) ، P (2) ، P (3) … … P (k) صحيحة لإثبات أن P (k + 1) صحيحة، عندما يفشل الحث الضعيف في إثبات بيان لجميع الحالات، فإننا نستخدم الاستقراء القوي، إذا كانت العبارة صحيحة للاستقراء الضعيف، فمن الواضح أنها صحيحة للحث الضعيف أيضًا. [3]

التبرير الاستقرائي

التبرير الاستقرائي والتخمين

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

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

ومع ذلك ، يمكنه إثبات فرضيته باستخدام وسائل أخرى والتوصل إلى نظرية (بيان مثبت)، في هذه الحالة، كما هو الحال في العديد من الحالات الأخرى، أدى التبرير الاستقرائي إلى الشك، أو بشكل أكثر تحديدًا، إلى فرضية انتهى بها الأمر إلى كونها صحيحة. [4]