✖

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

الاستقراء الرياضي طريقة برهان شائعة الاستخدام في الرياضيات، ونستخدمها غالباً عندما نتعامل مع الأعداد الطبيعية أو مع متتالية أخرى ما.

المبدأ

المبدأ الأساسي أن نبرهن العبارة المعطاة لعنصر أول ما، وهو في الأعداد الطبيعية غالباً n = 1 (نعني بالأعداد الطبيعية هنا الأعداد 1, 2, 3, …). ونبرهن ذلك بالتعويض المباشر. ثم نبرهن في الخطوة التالية، وهي خطوة الاستقراء، الاقتضاء «إذا كانت العبارة صحيحة عندما n = a، فإنها صحيحة أيضاً عندما n = a + 1».

ومن هاتين الخطوتين نستنتج أنّ العبارة المعطاة صحيحة لكل قيم n (من المجموعة التي نتعامل معها). فلماذا يكون ذلك؟ نبرهن في البداية أنّ العبارة صحيحة عندما n = 1. ونعرف أيضاً أنّ العبارة إذا صحّت عندما n = a، فإنها تصح عندما n = a + 1. فنختار a = 1. نعرف أنّ العبارة صحيحة عندما a = 1، ونعرف أيضاً أنها صحيحة عندما a + 1 = 2. فنعرف الآن أنّ العبارة صحيحة عندما a = 2. ولكن لأنها تصح أيضاً عند a + 1، فلا بد أن تصح عند 2 + 1 = 3. وهكذا.

المثال الأول

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

2∣2n

وتعني هذه الكتابة أنّ العدد اثنين يقسم العبارة 2n دون باقٍ. وما دمنا نعرف كيف نكتب قابلية القسمة، فيمكننا أن نكتب أيضاً ما علينا أن نبرهنه بالاستقراء الرياضي.

2∣2n+2;n∈N

هذا ما علينا أن نبرهنه في المثال الأول، أي أنّ العدد اثنين يقسم العبارة 2n + 2، وهو ما يوافق تماماً المطلوب الكلامي الأصلي: «إذا أضفنا العدد اثنين إلى أي عدد زوجي، حصلنا مرة أخرى على عدد زوجي».

في خطوة الأساس نبرهن ذلك للعنصر الأول، أي للواحد. نعوّض في العبارة n = 1:

2∣2×1+22∣4

العدد اثنان يقسم العدد أربعة دون باقٍ، إذن العبارة صحيحة للعنصر الأول. ثم تأتي خطوة الاستقراء، وفيها علينا أن نبرهن أنّ العبارة إذا صحّت للعنصر ذي الرتبة a، فإنها تصح أيضاً للعنصر ذي الرتبة (a + 1). نفترض في البداية صحة فرضنا، أي n = a:

2∣2a+2

نفترض أنّ هذه العبارة صائبة، وسنستخدمها في بناء البرهان. ونريد الآن أن نبرهن أنّ

2∣2(a+1)+2.

ماذا فعلنا؟ كتبنا (a + 1) مكان a. والمهم هنا الأقواس، فهذه العبارة مثلاً خاطئة: 2a + 1 + 2. فنحن لا نضيف واحداً إلى العبارة كلها، بل نجعل a حقاً أكبر بواحد، أي (a + 1). ونحوّل العبارة بفك القوس.

2∣2(a+1)+22∣2a+2+2 

ولنستطرد قليلاً إلى قابلية القسمة. إذا كان لدينا عددان، وليكونا p و q، يقبلان القسمة على عدد ما، وليكن r، فإنّ مجموعهما يقبل القسمة أيضاً على العدد r. أي:

(r∣p∧r∣q)⇒r∣(p+q)

يمكننا أن نعوّض مثلاً بالأعداد p = 8 و q = 20 و r = 4. نرى أنّ العدد أربعة يقسم العدد ثمانية والعدد عشرين، ويقسم كذلك مجموعهما 8 + 20 = 28.

فكيف نستفيد من ذلك في مثالنا؟ نقسم الطرف الأيمن إلى العددين p و q على النحو الآتي:

p=2a+2;q=2

العدد q، أي العدد اثنان، يقبل القسمة على اثنين بداهةً. والعبارة p تقبل القسمة أيضاً على اثنين، لأنّ الفرض يقول لنا ذلك. فالعبارة p توافق تماماً فرضنا الذي نفترض أنه صائب. وإذا كان p يقبل القسمة على اثنين وكان q يقبل القسمة على اثنين، فإنّ مجموعهما يقبل القسمة على اثنين أيضاً.

ولنعد مرة أخرى إلى الفرض. قلنا في البداية إننا نفترض صحة

2∣2a+2.

ولذلك عندما صادفنا العبارة 2a + 2 في أثناء بناء البرهان، أمكننا أن نقول إنها تقبل القسمة على اثنين، لأنها فرضنا بالذات. وهذه في العادة أصعب خطوة في الاستقراء الرياضي: أن نفهم متى ولماذا يمكننا أن نستخدم فرض الاستقراء.

وبهذا ينتهي الاستقراء، فقد تمّ البرهان بنجاح، والمبرهنة صحيحة.

ولو أردنا، لأمكننا أن نقسم العبارة بطريقة أخرى دون استخدام الفرض: p = 2n و q = 2 + 2. فالعدد q = 4 يقبل القسمة على اثنين بداهةً، وكذلك p = 2n؛ لأنه بعد القسمة على اثنين يبقى لنا العدد n، وهو عدد طبيعي، أي صحيح. فحصلنا مرة أخرى على عبارتين تقبل كل منهما القسمة على اثنين، إذن مجموعهما يقبل القسمة على اثنين أيضاً.

لكننا في الحالتين برهنّا أنّ

  1. العبارة المعطاة صحيحة عندما n = 1،
  2. إذا صحّت العبارة عند n، فإنها تصح عند n + 1.

ومن هنا نستنتج:

  • نعرف أنّ العبارة صحيحة عندما n = 1.
  • إذا صحّت عند n، فلا بد أن تصح عند n + 1، أي عند 1 + 1، أي أنّ العبارة صحيحة أيضاً عندما n = 2.
  • إذا صحّت عند n، فلا بد أن تصح عند n + 1، أي عند 2 + 1، أي أنّ العبارة صحيحة أيضاً عندما n = 3.
  • إذا صحّت عند n، فلا بد أن تصح عند n + 1، أي عند 3 + 1، أي أنّ العبارة صحيحة أيضاً عندما n = 4.
  • إذا صحّت عند n، فلا بد أن تصح عند n + 1، أي عند 4 + 1، أي أنّ العبارة صحيحة أيضاً عندما n = 5.
  • …

المثال الثاني

نبرهن الآن بالاستقراء الرياضي العبارة البسيطة:

2n≥2n;n∈N.

نبدأ بخطوة الأساس، فنتحقق هل العبارة صحيحة عندما n = 1، بوصفه العنصر الأول من الأعداد الطبيعية التي نختار منها n.

21≥2×12≥2

وهذا متحقق بداهةً. ننتقل الآن إلى خطوة الاستقراء، وفيها علينا أن نتحقق: إذا صحّت العبارة عندما n = a، فهل تصح أيضاً عندما n = a + 1؟ إذن فرضنا هو صحة

2a≥2a

ونريد أن نبرهن:

2a+1≥2(a+1)

نكتب الطرف الأيسر أولاً بقواعد الحساب بالقوى، ونفك القوس في الطرف الأيمن ببساطة.

2⋅2a≥2a+2

نستخدم في الطرف الأيسر الجمع بدلاً من الضرب، ونترك الطرف الأيمن دون تغيير.

2a+2a≥2a+2

نستخدم الآن الفرض، وهو العبارة التي نفترض صحتها. في المتباينة حدّان مجموعان في كل طرف. ونعرف في الوقت نفسه أنّ

2a≥2a2a≥2.

السطر الأول يقوله لنا الفرض، والعبارة الثانية بديهية (فأصغر قيمة للعبارة 2a تكون عندما a = 1، وهي تساوي اثنين). إذن نعرف أنّ كلاً من الحدين في الطرف الأيسر أكبر من الحد المقابل في الطرف الأيمن أو يساويه. وبذلك برهنّا بالاستقراء أنّ العبارة إذا صحّت عند a، فإنها تصح أيضاً عند (a + 1)، ولأنّ العبارة صحيحة أيضاً عند الواحد، فإنها صائبة.

المثال الثالث

لنحاول أن نبرهن العبارة الآتية:

3∣n⇒3∣n2;n∈N

أي بالكلمات: إذا كان n يقبل القسمة على ثلاثة، فإنّ n2 يقبل القسمة على ثلاثة أيضاً. فإذا كان n لا يقبل القسمة على ثلاثة، كانت العبارة صحيحة بداهةً (بحسب تعريف الاقتضاء)، ولذلك سنهتم بالحالات التي يكون فيها n قابلاً للقسمة على ثلاثة. وهذا يولّد لنا متتالية الأعداد الطبيعية ai = 3، 6، 9، 12، 15… ومن الآن فصاعداً سنتعامل مع هذه المتتالية ai.

نبدأ البرهان بالاستقراء بخطوة الأساس، أي نتحقق هل العبارة صحيحة للعنصر الأول. ونذكّر بأننا نتعامل مع المتتالية ai، فنأخذ العنصر الأول من هذه المتتالية، أي العنصر a1، وهو العدد ثلاثة. والعبارة صحيحة للعدد ثلاثة:

3∣3⇒3∣32

ننتقل الآن إلى خطوة الاستقراء. نرى أنّ المتتالية ai يمكن كتابتها على الصورة 3n، حيث n عدد طبيعي. أي أنّ العنصر الثاني أكبر من سابقه بثلاثة، وهكذا. لنفترض الآن أنّ العبارة صحيحة عند n، وعلينا أن نضمن أن تصح أيضاً عند (n + 3)، وهي القاعدة التي تولّد العنصر التالي في المتتالية التي نتعامل معها. نكتب أولاً الفرض:

3∣n⇒3∣n2

ثم ما نريد أن نبرهنه

3∣(n+3)⇒3∣(n+3)2.

نفك القوس في الطرف الآخر بالقانون:

3∣(n+3)⇒3∣n2+6n+9.

وقد اقتربنا من النهاية. ففي الطرف الأيسر عبارة تقبل القسمة على ثلاثة بالتأكيد؛ لأنّ n يقبل القسمة على ثلاثة بحسب الفرض (فنحن نتعامل فقط مع أعداد المتتالية ai)، والعدد ثلاثة يقبل القسمة على ثلاثة أيضاً. وفي الطرف الأيمن لدينا أولاً n2، وهو يقبل القسمة على ثلاثة بحسب الفرض. فنحن نعرف أنّ n يقبل القسمة على ثلاثة، والفرض يقول إنّ n إذا قبل القسمة على ثلاثة، فإنّ n2 يقبل القسمة على ثلاثة أيضاً:

3∣n⇒3∣n2

ثم يأتي الحد 6n، وهو يقبل القسمة على ثلاثة بداهةً. ويمكن تصور ذلك على أنه اختصار كسر:

6n3=2n

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

عدد الأقواس في العبارة

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

  • عدد طبيعي،
  • إذا كان p تعبيراً بسيطاً، فإنّ (p2) تعبير بسيط أيضاً،
  • إذا كان p و q تعبيرين بسيطين، فإنّ (p + q) تعبير بسيط أيضاً.

فهذه تعابير بسيطة: 12 و 54 و (5 + 6) و (12 + 7) و (62) و ((5 + 6)2). أما هذه فليست تعابير بسيطة:

  • 1 + 2 → تنقصه الأقواس الخارجية،
  • (1 + 2 → ينقصه القوس الأيمن،
  • 132 → تنقصه الأقواس الخارجية،
  • (1 + 2 + 3) → تنقصه أقواس، والكتابة الصحيحة (1 + (2 + 3))

ويمكن أن ينشأ التعبير البسيط مثلاً على النحو الآتي. نختار في البداية التعبير البسيط (a + b). نضع الآن مكان a التعبير البسيط a = (c + d)، فنحصل على ((c + d) + b)، ونضع مكان b العدد ثلاثة: ((c + d) + 3). ونضع مكان c العدد عشرة: ((10 + d) + 3)، وأخيراً نضع مكان d التعبير (52): ((10 + (52)) + 3). ومن المهم أن نحافظ على الأقواس، وإلا فلن تنجح الطريقة.

نبرهن الآن أنّ التعبير البسيط يحتوي على عدد زوجي من الأقواس (والصفر من الأعداد الزوجية أيضاً).

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

j=n;n∈N.

وعدد الأقواس في التعبير j صفر، إذن العنصر الأول يحقق العبارة. وفي خطوة الاستقراء نفترض أنّ لدينا تعبيرين بسيطين p و q، وأنّ في كل منهما عدداً زوجياً من الأقواس. وعلينا عندئذٍ أن نبرهن أنّ في التعبيرين البسيطين (p + q) و (p2) أيضاً عدداً زوجياً من الأقواس.

نبدأ بالجمع. نعرّف أيضاً الدالة z(q) التي تعطي عدد الأقواس في التعبير q. عندئذٍ يكون في التعبير (p + q) عدد من الأقواس يساوي z(p) + z(q) + 2، أي فيه قوسان أكثر من مجموع أقواس التعبيرين p و q. وبحسب الفرض كل من z(p) و z(q) زوجي، فإذا جمعنا ثلاثة أعداد زوجية، حصلنا مرة أخرى على عدد زوجي. فالعبارة صحيحة في هذه الحالة.

ننتقل الآن إلى القوة. يبقى الفرض أنّ التعبير البسيط p يحتوي على عدد زوجي من الأقواس. فيحتوي التعبير (p2) على z(p) + 2 من الأقواس، أي مرة أخرى على قوسين أكثر من التعبير p. وفي هذه الحالة أيضاً نجمع أعداداً زوجية، فتكون النتيجة زوجية.

العبارة صحيحة للعنصر الأول وصحيحة في خطوة الاستقراء، ولذلك فهي صائبة.

المحتويات: ما البرهان الرياضي, البرهان بالتناقض, الاستقراء الرياضي