البرهان بالاستدلال

القسم 4.5 البرهان بالاستدلال

الأهداف

بعد إتمام هذا القسم، ينبغي أن تتمكّن من فعل ما يلي.

أن تحدّد أجزاء برهان الاستدلال الرياضي (mathematical induction)، وكيف ترتبط هذه الأجزاء بالعبارة التي يجري إثباتها.
أن تثبت عباراتٍ باستعمال الاستدلال الرياضي.
أن تشرح لماذا يكون برهان الاستدلال الرياضي صحيحًا.

معاينة القسم

استكشف!

ما رقم الآحاد (أقصى رقمٍ إلى اليمين) في $6^n\text{?}$ وهل تعتمد الإجابة على $n\text{?}$

الاستدلال الرياضي تقنيةُ برهانٍ قوية يمكن استعمالها لإثبات صحّة العبارات لكل متتالية من العبارات، ما دامت تلك المتتالية من العبارات لها نقطةُ بداية. فمثلًا، إذا كنّا نحاول القول بشيءٍ ما عن رقم الآحاد في $6^n\text{,}$ فإنّنا نصنع هذه الدعوى عند $n=1\text{,}$ ثمّ عند $n = 2\text{,}$ ثمّ عند $n = 3\text{,}$ وهكذا.

ويرتبط الاستدلال ارتباطًا وثيقًا بالتعريفات التعاودية؛ إذ الفكرة الرئيسة في برهانٍ بالاستدلال هي أن تشرح كيف يمكنك الانتقال من عبارةٍ في المتتالية إلى العبارة التي تليها.

ورقة العمل: نشاط تمهيدي

1.

افترض أنّ $6^{472}$ رقمُ آحاده 2. أي، افترض $6^{472} = 19,381,6\ldots\ldots 2\text{.}$ فما رقمُ آحاد $6^{473}$ ؟

تلميح. $6^{473} = 6 \cdot 6^{472}\text{.}$

2.

ما رقمُ آحاد $6^{2}\text{,}$ ورقمُ آحاد $6^3\text{,}$ ورقمُ آحاد $6^4\text{?}$

رقمُ آحاد $6^2$ هو .

رقمُ آحاد $6^3$ هو .

رقمُ آحاد $6^4$ هو .

3.

أيٌّ ممّا يلي صحيح؟ حدّد كل ما ينطبق.

إذا كان رقمُ آحاد $6^k$ هو 6، فإنّ رقمَ آحاد $6^{k+1}$ هو 6.
إذا كان رقمُ آحاد $6^k$ هو 2، فإنّ رقمَ آحاد $6^{k+1}$ هو 2.
رقمُ آحاد $6^{472}$ هو 2.
رقمُ آحاد $6^{472}$ هو 6.

4.

اشرح إجابتك عن السؤال السابق.

قسم فرعي: التفكير التعاودي

لقد رأينا أنّ وصف متتاليةٍ تعريفًا تعاوديًّا يكون أسهل في كثيرٍ من الأحيان من وصفها بصيغةٍ مغلقة. وسنرى الآن كيف يساعدنا استعمال تفكيرٍ تعاوديٍّ مشابه على إثبات العبارات باستعمال تقنية برهانٍ تُدعى الاستدلال الرياضي. وهذا الأسلوب من البراهين مفيدٌ خصوصًا عندما تكون الحالات المختلفة للعبارة (لقيمٍ مختلفة من $n\text{,}$ مثلًا) مرتبطةً ارتباطًا تعاوديًّا.

فمثلًا، لنفترض أنّنا أردنا إثبات حقيقةٍ عن كلّ حدود متتاليةٍ لدينا تعريفٌ تعاوديٌّ لها. تأمّل المتتالية $(a_n)_{n\ge 0}$ المعرَّفة تعريفًا تعاوديًّا بواسطة $a_n = 3a_{n-1} - 2$ مع $a_0 = 5\text{.}$ فهل يمكننا إثبات أنّ كلّ حدٍّ في هذه المتتالية فرديّ؟

لنبدأ بكتابة الحدود الأولى القليلة في المتتالية: $\begin{equation*} 5, 13, 37, 109, \ldots\text{.} \end{equation*}$ حتى الآن، يبدو كلّ هذه الأعداد فردية. هل سيكون العدد التالي فرديًّا؟ بالطبع يمكننا حسابه ببساطة باستعمال العلاقة التعاودية. فنأخذ $3\cdot 109 - 2\text{.}$ ولا يهمّنا فعليًا أيّ عددٍ فرديٍّ يكون هو، فالمهمّ فقط أنّه فرديّ بالفعل. ونحن نعرف أنّه سيكون فرديًّا، لأنّ حاصل ضرب عددين فرديّين عددٌ فرديّ، ولأنّ طرح 2 من عددٍ فرديّ ينتج عددًا فرديًّا.

ممتاز، إذن $a_4$ فرديّ. هل $a_5$ فرديّ أيضًا؟ نعم، استعمل الحجة نفسها أعلاه: $a_5 = 3 a_4 - 2\text{.}$ لقد أقنعنا أنفسنا للتوّ بأنّ $a_4$ فرديّ (من دون أن نوجد قيمته الفعلية)، إذن $3 a_4$ فرديّ، وطرح 2 منه ينتج عددًا فرديًّا أيضًا.

وماذا عن $a_6\text{?}$ افعل الشيء نفسه. وفي الحقيقة، لماذا نستخدم أيّ عددٍ معيّنٍ دليلًا؟ فإذا كانت الحجة نفسها في كلّ مرّة، فينبغي أن نتمكن من إعطاء هذه الحجة مرّة واحدة فقط، ونقول إنّها تعمل دائمًا.

لنفترض أنّنا وجدنا أنّ $a_k$ فرديّ (حيث $k$ عددٌ طبيعيٌّ اعتباطيّ). ومن هذا يمكننا أن نجد أنّ $a_{k+1}$ فرديّ، إذ $a_{k+1} = 3 a_k - 2\text{,}$ وثلاثة أمثال العدد الفرديّ $a_{k}$ عددٌ فرديّ، وطرح 2 ينتج عددًا فرديًّا. أحسنت. لنجمع كلّ هذا معًا في برهان.

البرهان.

نُدّعي أنّه لكل $n \ge 0\text{,}$ يكون العدد $a_n$ فرديًّا، حيث $a_n = 3a_{n-1} - 2$ و $a_0 = 5\text{.}$

عندما $n = 0\text{,}$ تكون الدعوى صادقة، إذ $a_0 = 5$ عددٌ فرديّ.

وفضلاً عن ذلك، يمكننا إثبات أنّ كلّ $n$ أكبر يكون له $a_n$ فرديًّا، لأنّ ما دام $a_k$ فرديًّا فإنّ $a_{k+1}$ فرديّ أيضًا (إذ $a_{k+1} = 3a_{k} - 2\text{,}$ وثلاثة أمثال عددٍ فرديّ ناقص 2 هو دائمًا عددٌ فرديّ).

إذن $a_n$ فرديّ لكل $n \ge 0\text{.}$

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

قسم فرعي: صياغة البراهين

يستطيع الاستدلال إثبات عباراتٍ كثيرةٍ تصدق لكلّ الأعداد الطبيعية، لا مجرّد عباراتٍ عن المتتاليات. وبشكل خاصّ، ينبغي استعمال الاستدلال عندما ثمّة طريقةٌ للانتقال من حالةٍ إلى التي تليها — عندما تستطيع أن ترى كيف تفعل «واحدًا أكثر» في كلّ مرّة.

وفي تفكيرنا في كيفية كتابة العبارات بالرموز المنطقية، سنستعمل الاستدلال لإثبات عباراتٍ من الشكل $\begin{equation*} \forall n P(n)\text{,} \end{equation*}$ حيث يكون لمجال الخطاب (قيم $n$ التي نُكمِّم عنها) أصغرُ عنصر. لنقل إنّ مجال الخطاب هو الأعداد الطبيعية. عندئذٍ نُثبت هذه المتتالية من العبارات: $\begin{equation*} P(0), P(1), P(2), P(3), \ldots\text{.} \end{equation*}$ والطريقة التي نفعل ذلك بها بالاستدلال هي إثبات حالةٍ أساسية، namely أنّ $P(0)$ صادقة (أو $P(a)$ حيث $a$ أصغرُ عنصرٍ في مجال الخطاب لدينا). ثمّ نثبت الحالة الاستقرائية، namely أنّ $P(k) \imp P(k+1)$ لكل $k \ge 0$ (أو $k \ge a$ ).

وهذان معًا كافيان لإثبات أنّ $P(n)$ صادقة لكلّ $n\text{.}$ وكيف نعرف ذلك؟ أي، لماذا يكون هذا الأسلوب من البرهان صحيحًا؟ حسنًا، لنقنع أنفسنا بأنّ $P(3)$ صادقة. نحن نعرف أنّ $P(0)$ صادقة. ولأنّنا نعرف أنّ $P(0) \imp P(1)\text{,}$ فإنّنا نعرف أيضًا أنّ $P(1)$ صادقة. ولأنّ $P(1) \imp P(2)\text{,}$ فإنّنا نجد أنّ $P(2)$ صادقة. وأخيرًا، ولأنّ $P(2) \imp P(3)\text{,}$ فإنّ لدينا $P(3)\text{.}$ وليس في 3 هنا شيءٌ مميّز. يمكننا أن نصعد إلى أيّ حدٍّ نشاء، إلى أيّ قيمةٍ لـ $n$ !

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

الاستدلال قويّ! وتأمّل كم يكون إسقاط القطع أسهل حين لا تضطرّ إلى دفع كلّ قطعةٍ بنفسك. إنّك تكتفي ببدء سلسلة التفاعل ثمّ تعتمد على تقارب القطع النسبيّ ليتولّى الباقي.

وعند كتابة برهانٍ بالاستدلال، سنتّبع أسلوبًا معياريًّا. فالكتابة بهذا الأسلوب تتيح لنا إبقاء أفكارنا منظّمة، وقد تساعدنا حتى في صياغة البرهان.

وإليك البنية العامة لبرهانِ بالاستدلال الرياضي:

بنية برهان الاستدلال.

ابدأ بذكر ما هي العبارة التي تريد إثباتها: «دع $P(n)$ تكون العبارة….» ولإثبات أنّ $P(n)$ صادقة لكل $n \ge 0\text{,}$ لا بدّ من إثبات حقيقتين:

الحالة الأساسية: اثبت أنّ $P(0)$ صادقة. فأنت تفعل ذلك مباشرةً، وهذه الخطوة غالبًا ما تكون سهلة.
الحالة الاستقرائية: اثبت أنّ $P(k) \imp P(k+1)$ لكل $k \ge 0\text{.}$ أي، اثبت أنّه لكل $k \ge 0$ إذا كانت $P(k)$ صادقة فإنّ $P(k+1)$ صادقة أيضًا. وهذا هو برهان عبارةٍ من شكل «إذا … فإنّ …»، ولذلك يمكنك أن تفترض أنّ $P(k)$ صادقة (ويُشار إلى $P(k)$ بأنّها فرضية الاستقراء). ثمّ عليك أن تشرح لماذا تكون $P(k+1)$ صادقة أيضًا، انطلاقًا من ذلك الافتراض.

بافتراض نجاحك في كلا الجزأين أعلاه، يمكنك أن تستنتج: «إذن، بمبدأ الاستدلال الرياضي، تكون العبارة $P(n)$ صادقة لكل $n \ge 0\text{.}$ »

قد لا تكون العبارة $P(n)$ صادقة إلا لقيم $n \ge 4\text{,}$ مثلًا، أو لقيمةٍ أخرى. وفي هذه الحالات، استبدل كلَّ الأصفار أعلاه بالأربعات (أو بالقيمة الأخرى).

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

قسم فرعي: أمثلة

إليك بعض أمثلة البرهان بالاستدلال الرياضي.

المثال 4.5.1.

اثبت أنّه لكلّ عددٍ طبيعيّ $n \ge 1$ يكون $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\text{.}$

الحل. أوّلًا، لنفكّر في هذه المعادلة تفكيرًا استقرائيًّا. وفي الحقيقة، نحن نعرف أنّ هذا صحيح بسببٍ آخر (العكس والجمع يخطر على البال). لكنّ لماذا قد يكون الاستدلال منطبقًا؟ فالطرف الأيسر يجمع الأعداد من 1 إلى $n\text{.}$ فإذا كنّا نعرف كيف نفعل ذلك، فإنّ إضافة حدٍّ واحدٍ آخر ( $n+1$ ) لن تكون صعبةً البتّة. فمثلًا، إذا كان $n = 100\text{,}$ فافترض أنّنا نعرف أنّ مجموع الأعداد المئة الأولى هو $5050$ (أي $1 + 2 + 3 + \cdots + 100 = 5050\text{,}$ وهذا صحيح). والآن لإيجاد مجموع الأعداد المئة والأول، يكون من الأنسب أن نضيف 101 إلى 5050 بدلًا من حساب المجموع كلّه من جديد. فسنحصل على $1 + 2 + 3 + \cdots + 100 + 101 = 5050 + 101 = 5151\text{.}$ وفي الحقيقة، من السهل دائمًا إضافة حدٍّ واحدٍ آخر فقط. ولهذا ينبغي أن نستعمل الاستدلال.

والآن البرهان الرسمي:

البرهان.

دع $P(n)$ تكون العبارة $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\text{.}$ وسنُبيّن أنّ $P(n)$ صادقة لكلّ الأعداد الطبيعية $n \ge 1\text{.}$

الحالة الأساسية: $P(1)$ هي العبارة $1 = \frac{1(1+1)}{2}$ وهي صادقة بوضوح.

الحالة الاستقرائية: لتكن $k \ge 1$ عددًا طبيعيًّا. افترض (لأجل الاستدلال) أنّ $P(k)$ صادقة. أي إنّ $1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}\text{.}$ وسنُثبت أنّ $P(k+1)$ صادقة أيضًا. أي إنّنا يجب أن نُثبت أنّ $1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\text{.}$ ولإثبات هذه المعادلة، ابدأ بإضافة $k+1$ إلى طرفي فرضية الاستقراء: $\begin{equation*} 1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)\text{.} \end{equation*}$

والآن، بتبسيط الطرف الأيمن نحصل على: $\begin{align*} \frac{k(k+1)}{2} + k+1 \amp = \frac{k(k+1)}{2} + \frac{2(k+1)}{2}\\ \amp = \frac{k(k+1) + 2(k+1)}{2}\\ \amp = \frac{(k+2)(k+1)}{2}\text{.} \end{align*}$

) صادقة، فبمبدأ الاستدلال الرياضي تكون $P(n)$ صادقة لكلّ الأعداد الطبيعية $n \ge 1\text{.}$

لاحظ أنّه في الجزء الذي اثبتُّ فيه $P(k+1)$ انطلاقًا من $P(k)\text{,}$ استعملنا المعادلة $P(k)\text{.}$ وهذه كانت فرضية الاستقراء. وعادةً ما تكون كيفية استعمال فرضيات الاستقراء سهلةً ومباشرةً عند إثبات حقيقةٍ عن مجموعٍ مثل هذا. وفي براهين أخرى، قد يكون موضعها أقلّ وضوحًا.

المثال 4.5.2.

اثبت أنّه لكل $n \in \N\text{,}$ يكون $6^n - 1$ مضاعفًا لـ 5.

الحل. ومرةً أخرى، ابدأ بفهم ديناميكية المسألة. ماذا يفعل زيادة $n$ ؟ لنجرّب بعض الأمثلة. إذا كان $n = 1\text{,}$ فنعم، $6^1 - 1 = 5$ مضاعف لـ 5. وماذا يبدو الأمر عند زيادة $n$ إلى 2؟ فنحصل على $6^2 - 1 = 35\text{,}$ وهو أيضًا مضاعف لـ 5. ثمّ $n = 3\text{:}$ لكن بدلًا من مجرّد إيجاد $6^3 - 1\text{,}$ ما الذي فعلته زيادة $n$ ؟ إنّنا ما زلنا نطرح 1، لكنّنا الآن نضرب في 6 أوّلًا. ونظرًا لها من زاويةٍ أخرى، فإنّنا نضرب في 6 عددًا يزيد بمقدار 1 عن مضاعفٍ لـ 5 (لأنّ $6^2 - 1$ مضاعف لـ 5، إذن $6^2$ يزيد بمقدار 1 عن مضاعفٍ لـ 5). وكيف تبدو الأعداد التي يزيد مقدارها بمقدار 1 عن مضاعفٍ لـ 5؟ لا بدّ أن ينتهي رقمها بـ 1 أو بـ 6. وماذا يحدث عند ضرب مثل هذا العدد في 6؟ يعتمد ذلك على العدد، لكن على أيّ حالٍ لا بدّ أن ينتهي الرقم الجديد بـ 6. ثمّ إن طرحنا 1، حصلنا على رقمٍ ينتهي بـ 5، أي مضاعف لـ 5.

والمقصود أنّه كلّما ضربنا في 6 واحدًا إضافيًا، نحصل على عددٍ ينتهي رقمه بـ 6، فطرح 1 يعطينا مضاعفًا لـ 5. والآن البرهان الرسمي:

البرهان.

دع $P(n)$ تكون العبارة: « $6^n - 1$ مضاعف لـ 5.» وسنُثبت أنّ $P(n)$ صادقة لكل $n \in \N\text{.}$

الحالة الأساسية: $P(0)$ صادقة: $6^0 -1 = 0\text{,}$ وهذا مضاعف لـ 5.

الحالة الاستقرائية: لتكن $k$ عددًا طبيعيًّا اعتباطيًّا. افترض، لأجل الاستدلال، أنّ $P(k)$ صادقة. أي إنّ $6^k - 1$ مضاعف لـ $5\text{.}$ عندئذٍ يكون $6^k - 1 = 5j$ لأجل عددٍ صحيح $j$ ما. وهذا يعني أنّ $6^k = 5j + 1\text{.}$ اضرب الطرفين في $6\text{:}$ $\begin{equation*} 6^{k+1} = 6(5j+1) = 30j + 6\text{.} \end{equation*}$

لكنّنا نريد أن نعرف عن $6^{k+1} - 1\text{,}$ فاطرح 1 من الطرفين: $\begin{equation*} 6^{k+1} - 1 = 30j + 5\text{.} \end{equation*}$

وبالطبع $30j+5 = 5(6j+1)\text{,}$ فهو مضاعف لـ 5.

مضاعف لـ 5، أو بمعنى آخر، $P(k+1)$ صادقة. إذن، بمبدأ الاستدلال الرياضي، تكون $P(n)$ صادقة لكل $n \in \N\text{.}$

اضطررنا إلى قدرٍ من الذكاء (أي استعمال بعض الجبر) كي نُحدّد موضع $6^k - 1$ داخل $6^{k+1} - 1$ قبل أن نتمكّن من تطبيق فرضية الاستقراء. وهذا ما يجعل براهين الاستدلال صعبة أحيانًا.

وفي المثالين أعلاه بدأنا بـ $n = 1$ أو بـ $n = 0\text{.}$ ويمكننا أن نبدأ لاحقًا إذا احتجنا إلى ذلك.

المثال 4.5.3.

اثبت أنّ $n^2 \lt 2^n$ لكل الأعداد الصحيحة $n \ge 5\text{.}$

الحل. أوّلًا، فكرةُ الحجة. ماذا يحدث عندما نزيد $n$ بمقدار 1؟ في الطرف الأيسر، نزيد أسّ المربّع فننتقل إلى العدد المربّع التالي. وفي الطرف الأيمن، نزيد أُسّ 2. وهذا يعني أنّنا نضاعف العدد. فالسؤال هو: ما علاقة مضاعفةِ عددٍ بالانتقال إلى المربّع التالي؟ فكّر في شكل الفرق بين مربّعين متتاليين. لدينا $(n+1)^2 - n^2\text{.}$ وهذا يُحَلَّل إلى: $\begin{equation*} (n+1)^2 - n^2 = (n+1-n)(n+1+n) = 2n+1\text{.} \end{equation*}$

لكنّ مضاعفة الطرف الأيمن تزيده بمقدار $2^n\text{,}$ إذ $2^{n+1} = 2^n + 2^n\text{.}$ وحين يكون $n$ كبيرًا بما يكفي، يكون $2^n > 2n + 1\text{.}$

والمقصود بقولنا هنا إنّه كلّما زاد $n$ ، ينمو الطرف الأيسر بمقدارٍ أقلّ من الطرف الأيمن. فإذا بدأ الطرف الأيسر أصغر (كما هو الحال عندما $n = 5$ )، فلن يلحق بالطرف الأيمن أبدًا. والآن البرهان الرسمي:

البرهان.

دع $P(n)$ تكون العبارة $n^2 \lt 2^n\text{.}$ وسنُثبت أنّ $P(n)$ صادقة لكل الأعداد الصحيحة $n \ge 5\text{.}$

الحالة الأساسية: $P(5)$ هي العبارة $5^2 \lt 2^5\text{.}$ وبما أنّ $5^2 = 25$ و $2^5 = 32\text{,}$ فإنّنا نرى أنّ $P(5)$ صادقة بالفعل.

الحالة الاستقرائية: لتكن $k \ge 5$ عددًا صحيحًا اعتباطيًّا. افترض، لأجل الاستدلال، أنّ $P(k)$ صادقة. أي، افترض $k^2 \lt 2^k\text{.}$ وسنُثبت أنّ $P(k+1)$ صادقة، أي $(k+1)^2 \lt 2^{k+1}\text{.}$ ولإثبات مثل هذه المتراجحة، ابدأ من الطرف الأيسر وتّجه نحو الطرف الأيمن: $\begin{align*} (k+1)^2 \amp = k^2 + 2k + 1 \amp\\ \amp \lt 2^k + 2k + 1 \amp \ldots\text{by the inductive hypothesis.}\\ \amp \lt 2^k + 2^k \amp \ldots\text{ since } 2k + 1 \lt 2^k \text{ for }k \ge 5.\\ \amp = 2^{k+1}. \amp \end{align*}$

^2 \lt 2^{k+1}\text{,}) بمعنى آخر $P(k+1)\text{.}$ إذن بمبدأ الاستدلال الرياضي تكون $P(n)$ صادقة لكل $n \ge 5\text{.}$

قد يذكّرك المثال السابق بـمبدأ مضمار السباق (racetrack principle) في التفاضل والتكامل، الذي يقول إن كان $f(a) \lt g(a)\text{,}$ و $f'(x) \lt g'(x)$ لكل $x > a\text{,}$ فإنّ $f(x) \lt g(x)$ لكل $x > a\text{.}$ الفكرة نفسها: فالدالّة الأكبر تنمو أكثر من الدالّة الأصغر، فتبقى الدالّة الأكبر أكبر. وفي الرياضيات المتقطّعة لا لدينا مشتقّات، فننظر إلى الفروق. إذن الاستدلال هو السبيل.

تحذير.

مع القوّة العظيمة تأتي المسؤولية العظيمة. الاستدلال ليس سحرًا. يبدو قويًّا جدًّا أن نتمكّن من افتراض أنّ $P(k)$ صادقة. فبعد كلّ ما قلناه، نحن نحاول إثبات أنّ $P(n)$ صادقة، والفرق الوحيد هو في المتغيّر: $k$ مقابل $n\text{.}$ فهل نفترض أنّ ما نريد إثباته صادق؟ ليس الأمر كذلك تمامًا. فنحن نفترض أنّ $P(k)$ صادقة لمجرّد لغرض إثبات أنّ $P(k+1)$ صادقة.

لكنّك قد تبدأ في الاعتقاد بأنّ بوسعك إثبات أيّ شيءٍ بالاستدلال. تأمّل هذا «البرهان» الخاطئ القائل إنّ لكل كنديّ لونَ عيونٍ واحدًا: دع $P(n)$ تكون العبارة القائلة إنّ أيّ $n$ من الكنديّين لهم لونُ عيونٍ واحد. $P(1)$ صادقة، لأنّ كلّ شخصٍ له لونُ عيونه هو. والآن افترض أنّ $P(k)$ صادقة. أي، افترض أنّه في أيّ مجموعةٍ من $k$ كنديّ، لونُ عيون الجميع واحد. والآن تأمّل مجموعةً اعتباطيةً من $k+1$ كنديًّا. يجب أن يكون لأوّل $k$ منهم لونُ عيونٍ واحد، لأنّ $P(k)$ صادقة. وكذلك يجب أن يكون لآخر $k$ منهم لونُ عيونٍ واحد، لأنّ $P(k)$ صادقة. فالحقيقة أنّ لونَ عيون الجميع في المجموعة يجب أن يكون واحدًا. إذن $P(k+1)$ صادقة. فبمبدأ الاستدلال الرياضي تكون $P(n)$ صادقة لكل $n\text{.}$

ومن الواضح أنّ خطأً ما قد وقع. والمشكلة أنّ البرهان الذي يُثبت أنّ $P(k)$ تستلزم $P(k+1)$ يفترض ضمنًا أنّ $k \ge 2\text{.}$ فنحن لم نُثبِت سوى أنّ $P(1)$ صادقة. وفي الحقيقة $P(2)$ خاطئة. جرّب هذا: اقرأ الفقرة السابقة مرّةً أخرى، مع استبدال $1$ مكان كل $k\text{.}$ فهل تستطيع تحديد الخطأ في تلك الحجة؟

أسئلة القراءة

1.

لنفترض أنّك أردت إثبات، باستعمال الاستدلال الرياضي، أنّ $1+3+5+\cdots+2n-1 = n^2$ لكل قيم $n \ge 1\text{.}$ فأيٌّ ممّا يلي سيكون السطر الأول المناسب من البرهان؟ حدّد كل ما ينطبق.

دع $P(n)$ تكون العبارة « $1+3+5+\cdots+2n-1 = n^2\text{.}$ »
صحيح. ولاحظ على وجه الخصوص أنّنا لا ندفع «لكل $n \ge 1$ » ضمن تعريف $P(n)\text{.}$
لكل $n \ge 1\text{,}$ دع $P(n)$ تكون العبارة: «مجموع الأعداد الفردية الأولى $n$ يساوي $n^2\text{.}$ »
هذا صحيح. ولاحظ أنّ القول إنّنا نعرّف $P(n)$ لكل $n\ge 1$ يختلف عن القول إنّ $P(n)$ تتضمّن «...لكل $n\ge 1\text{.}$ »
افترض $1+3+\cdots + 2n-1 = n^2$ لكل $n \ge 1\text{.}$
هذا هو ما تحاول إثباته، فلا يمكنك افتراضه. لاحقًا في البرهان (في الحالة الاستقرائية) سنفترض أنّ $P(k)$ صادقة لـ $k$ اعتباطيّ ما، لكنّ هذا ليس افتراضًا أنّها صادقة لكل $n$ دفعةً واحدة.
دع $P(n)$ تكون العبارة: « $1+3+\cdots+2n-1 = n^2$ لكل $n \ge 1\text{.}$ »
هذا لا معنى له: فما $P(3)$ ؟ أأنّ $1 + 3 + 5 = 3^2$ لكل $3 \ge 1\text{??}$
بما أنّ $P(1) = 1 = 1^2\text{,}$ فإنّ الحالة الأساسية صادقة.
هناك مشكلتان هنا: أوّلًا، عليك أن تذكر ما هي $P(n)$ . ثانيًا، $P(1)$ عبارةٌ، فلا يمكن أن تساوي العدد 1.

2.

لنفترض أنّك أردت إثبات أنّ $P(n,3) \ge \binom{n}{3}$ لكل $n \ge 4\text{.}$ اكتب السطر الأول من برهانٍ بالاستدلال.

3.

ما الأسئلة التي لديك؟ اكتب سؤالًا واحدًا على الأقلّ عن محتوى هذا القسم قد يثير فضولك أو يثير فضول زميلٍ لك بعد قراءة هذا القسم.

تمارين: مسائل تدريبية

1.

لنفترض أنّك تحاول إثبات، بالاستدلال الرياضي، أنّ عبارةً $P(n)$ صادقة لكل $n \ge 0\text{.}$ فما الذي ستحاول إثباته في خطوة الاستدلال من البرهان؟ (حدّد كل ما ينطبق.)

أنّه بافتراض أنّ $P(k)$ صادقة لـ $k \ge 0$ اعتباطيّ، يمكننا إثبات أنّ $P(k+1)$ صادقة.
أنّ $P(k)$ تستلزم $P(k+1)$ لكل $k \ge 0\text{.}$
أنّه بافتراض أنّ $P(k+1)$ صادقة لـ $k \ge 0$ اعتباطيّ، يمكننا إثبات أنّ $P(k)$ صادقة.
أنّ $P(k+1)$ تستلزم $P(k)$ لكل $k \ge 0\text{.}$
أنّ $P(k)$ تستلزم $P(k+1)$ لـ $k \ge 0$ واحدٍ على الأقلّ.

2.

لنفترض أنّك أردت إثبات العبارة التالية: $\begin{equation*} 2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ for all } n \ge 1\text{.} \end{equation*}$ فما السطر الأول في برهانٍ بالاستدلال؟

دع $P(n)$ تكون العبارة « $2 + 4 + 6 + \cdots + 2n = n(n+1)\text{.}$ »
دع $P(n)$ تكون العبارة « $2 + 4 + 6 + \cdots + 2n = n(n-1)$ لكل $n \ge 1\text{.}$ »
افترض أنّ $P(n)$ صادقة لكل $n \ge 1\text{.}$
دع $P(n) = 2 + 4 + 6 + \cdots + 2n\text{.}$
افترض أنّ $P(n) = n(n+1)$ لكل $n \ge 1\text{.}$

3.

لنفترض أنّك كنت تثبت العبارة التالية بالاستدلال الرياضي: $\begin{equation*} 2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ for all } n \ge 1\text{.} \end{equation*}$ فما الذي عليك أن تُظهره لإثبات الحالة الأساسية؟

أن تُظهر أنّ $P(1)$ صادقة. أي، أن تُظهر أنّ $2 = 1(1+1)\text{.}$
أن تُظهر أنّ $P(2)$ صادقة. أي، أن تُظهر أنّ $2 + 4 = 2(2+1)\text{.}$
أنّ المجموع يبدأ بـ $2\text{,}$ فإنّ عليك أن تأخذ أصغر $n$ تكون عنده العبارة $P(n)$ صادقة.
أن تُظهر أنّ $P(1)$ و $P(2)$ صادقتان معًا.
أن تُظهر أنّ $P(1)$ تستلزم $P(2)\text{.}$
لا شيء، لأنّ المجموع يحتوي أصلًا على أكثر من $n = 1$ حدًّا.

4.

لنفترض أنّك كنت تثبت العبارة التالية بالاستدلال الرياضي: $\begin{equation*} 2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ for all } n \ge 1\text{.} \end{equation*}$ فما السطر الأول من الحالة الاستقرائية؟

افترض أنّ $P(k)$ صادقة لـ $k \ge 1$ اعتباطيّ ما، أي افترض $2+4+6+\cdots + 2k = k(k+1)\text{.}$
افترض أنّ $P(k)$ صادقة لكل $k \ge 1\text{,}$ أي افترض $2+4+6+\cdots + 2k = k(k+1)\text{.}$
افترض أنّ $P(k)$ و $P(k)$ صادقتان معًا لـ $k \ge 1$ اعتباطيّ؛ أي افترض $2+4+6+\cdots + 2k = k(k+1)$ و $2+4+6+\cdots + 2k+ 2k+2) = (k+1)(k+2)\text{.}$
افترض أنّ $P(k)$ تستلزم $P(k+1)$ لـ $k \ge 1$ اعتباطيّ.
افترض أنّ $P(k)$ صادقة لـ $k \ge 1$ كبيرٍ ما؛ قل، افترض $2 + 4 + 6 + \cdots + 432 = 216(217)\text{.}$

5.

رتّب بعض العبارات التالية لتُكوّن برهانًا صحيحًا بالاستدلال يُثبت أنّ العلاقة التعاودية $a_n = 5a_{n-1} + 4\text{,}$ مع الشرط الابتدائي $a_0 = 0$ لها صيغة مغلقة $a_n = 5^n - 1\text{.}$

لتكن \(P(n)\) هي العبارة «\(a_n = 5^n - 1\)».
---
لاحظ أنّ \(a_0 = 5^0 - 1 = 0\text{,}\) ولذلك \(P(0)\) صادقة.
---
ولنفترض الآن أنّ \(P(k)\) صادقة لعددٍ صحيحٍ اعتباطيّ \(k \ge 0\text{.}\)
---
إذن \(a_k = 5^k - 1\text{.}\)
---
ومن العلاقة التعاودية لدينا \(a_{k+1} = 5 a_k + 4 = 5 (5^k -1) + 4\text{.}\)
---
وهذا يبسّط إلى \(a_{k+1} = 5^{k+1} - 5 + 4 = 5^{k+1} - 1\text{,}\) ولذلك \(P(k+1)\) صادقة.
---
إذن، بمبدأ الاستدلال الرياضي، \(P(n)\) صادقة لكل \(n \ge 0\text{.}\)
---
ولنفترض الآن أنّ \(P(k+1)\) صادقة لعددٍ صحيحٍ اعتباطيّ \(k \ge 0\text{.}\)
---
إذن \(a_{k+1} = 5a_k+4\text{,}\) ولذلك \(P(k+1)\) صادقة.

6.

رتّب بعض العبارات التالية لتُكوّن برهانًا صحيحًا بالاستدلال يُثبت أنّه لكل $n \ge 1\text{,}$ يكون العدد $14^n - 1$ مضاعفًا لـ $13\text{.}$

لتكن \(P(n)\) هي العبارة «\(14^n - 1\) من مضاعفات \(13\text{.}\)»
---
لاحظ أنّ \(14^1 - 1 = 13\text{,}\) فهذا بالتأكيد من مضاعفات \(13\text{.}\)
---
ولنفترض الآن أنّ \(P(k)\) صادقة لعددٍ صحيحٍ اعتباطيّ \(k \ge 1\text{.}\)
---
إذن \(14^k - 1 = 13\cdot j\) لأيّ عددٍ صحيحٍ ما \(j\text{.}\)
---
ولأنّ \(14^{k+1} - 1 = 14(14^k - 1) + 14 - 1 = 14(13\cdot j) + 13\text{,}\) نرى أنّ \(14^{k+1} - 1\) من مضاعفات \(13\text{.}\)
---
ومن ثمّ \(P(k+1)\) صادقة.
---
إذن، بمبدأ الاستدلال الرياضي، \(P(n)\) صادقة لكل \(n \ge 1\text{.}\)
---
لاحظ أنّ \(14^2 - 1 = (14-1)(14+1)\) بفرق المربّعات، فهذا من مضاعفات 13.
---
ولنفترض الآن أنّ \(P(n)\) صادقة لكل \(n \ge 1\text{.}\)
---
ومن ثمّ \(14^k = \frac{14^{k+1} - 1}{14}\text{,}\) ولا بدّ أن يكون أيضًا من مضاعفات 13.

7.

رتّب بعض العبارات التالية لتُكوّن برهانًا صحيحًا بالاستدلال يُثبت أنّه لكل $n \ge 1\text{,}$ يكون $1+1+2+3+5+\cdots + F_n = F_{n+2} - 1\text{,}$ حيث $F_n$ هو العدد رقم $n$ في متتالية فيبوناتشي (Fibonacci numbers).

لتكن \(P(n)\) هي العبارة «\(1+1+2+3+5+\cdots + F_n = F_{n+2} - 1\text{.}\)»
---
أمّا الحالة الأساسية، فلاحظ أنّ \(P(1)\) و\(P(2)\) صادقتان، لأنّ \(1 = 2-1\) و\(1+1 = 3-1\text{.}\)
---
ولنفترض الآن أنّ \(P(k)\) صادقة لعددٍ صحيحٍ اعتباطيّ \(k \ge 2\text{.}\)
---
أي، نفترض أنّ \(1+1+2+3 + 5+F_k = F_{k+2} - 1\text{.}\)
---
ثمّ بإضافة \(F_{k+1}\) إلى الطرفين نحصل على \(1+1+2+3+5+\cdots + F_k + F_{k+1} = F_{k+1} + F_{k+2} - 1\text{.}\)
---
وبتعريف أعداد فيبوناتشي، \(F_{k+1} + F_{k+2} = F_{k+3}\text{,}\) فيبسّط الطرف الأيمن إلى \(F_{k+3} - 1\text{.}\)
---
ومن ثمّ \(P(k+1)\) صادقة، وإذن بمبدأ الاستدلال الرياضي تكون \(P(n)\) صادقة لكل \(n \ge 1\text{.}\)
---
أمّا الحالة الأساسية، فلاحظ أنّ \(1+1+2 = 4 = F_{5}-1\text{.}\)
---
ثمّ بحكم فرضية الاستدلال، \(1+1+2+3+\cdots+F_{k+1} = F_{k+2} - 1\text{.}\)
---
وطرح \(F_{k+1}\) من الطرفين يعطينا \(P(k)\text{,}\) وهو ما افترضنا هو أيضًا صادقة.

تمارين: تمارين إضافية

1.

في طريقك إلى السوق، تستبدل بقرتك بعض حبّات البُنّ الإسبريسو السحريّة المصنوعة من الشوكولاتة الداكنة. ولهذه الحبّات خاصيةٌ مفادها أنّ كلَّ ليلةٍ عند منتصف الليل ينقسم كلُّ حبّةٍ إلى اثنتين، فتتضاعف مجموعتك فعليًّا. فتقرّر أن تستفيد من هذا، وأنّك كلَّ صباحٍ (حوالي الساعة 8 صباحًا) تأكل 5 حبّات.

اشرح لماذا صحيح أنّه إذا كنت في ظهر اليوم $n$ تملك عددًا من الحبّات ينتهي بـ 5، فإنّك في ظهر اليوم $n+1$ ما زلت تملك عددًا من الحبّات ينتهي بـ 5.
لماذا لا تكفي الحقيقة السابقة للاستنتاج أنّك ستظلّ دائمًا تملك عددًا من الحبّات ينتهي بـ 5؟ وما الحقيقة الإضافية التي ستحتاجها؟
بافتراض أنّ لديك الحقيقة الإضافية في الجزء (b)، وأنّك أثبتت بنجاح الحقيقة في الجزء (a)، فكيف تعرف أنّك ستظلّ دائمًا تملك عددًا من الحبّات ينتهي بـ 5؟ وضح ما يحدث بشرحٍ دقيق لكيفية إثبات الحقيقتين أعلاه أنّك ستملك عددًا من الحبّات ينتهي بـ 5 في اليوم 4 تحديدًا. بمعنى آخر، اشرح لماذا يعمل الاستدلال في هذا السياق.

2.

استعمل الاستدلال لإثبات أنّه لكل $n \in \N$ يكون $\d\sum_{k=0}^n 2^k = 2^{n+1} - 1\text{.}$

3.

اثبت أنّ $7^n - 1$ مضاعف لـ 6 لكل $n \in \N\text{.}$

4.

اثبت أنّ $1 + 3 + 5 + \cdots + (2n-1) = n^2$ لكل $n \ge 1\text{.}$

5.

اثبت أنّ $F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$ حيث $F_n$ هو العدد رقم $n$ في متتالية فيبوناتشي.

6.

اثبت أنّ $2^n \lt n!$ لكل $n \ge 4\text{.}$ (تذكّر أنّ $n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n\text{.}$ )

7.

اثبت، بالاستدلال الرياضي، أنّ $F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\text{,}$ حيث $F_n$ هو العدد رقم $n$ في متتالية فيبوناتشي ( $F_0 = 0\text{,}$ $F_1 = 1$ و $F_n = F_{n-1} + F_{n-2}$ ).

8.

زومبي أويلر وزومبي كوشي، عالمان رياضيّان مشهوران من الزومبي، سجّلا للتوّ حسابات على Myspace. وبعد يومٍ واحد، يكون لدى زومبي كوشي متابعون أكثر من زومبي أويلر. وفي كلّ يومٍ بعد ذلك، يكون عدد المتابعين الجدد لزومبي كوشي مساويًا تمامًا لعدد المتابعين الجدد لزومبي أويلر (ولا يفقد أيٌّ منهما أيّ متابع). اشرح كيف يمكن لبرهانٍ بالاستدلال الرياضي أن يُظهر أنّه في كلّ يومٍ بعد اليوم الأول، يكون لدى زومبي كوشي متابعون أكثر من زومبي أويلر. أي، اشرح ما هي الحالة الأساسية والحالة الاستقرائية، ولماذا يُثبتان معًا أنّ لدى زومبي كوشي متابعين أكثر في اليوم الرابع.

9.

أوجد أكبر عددٍ من النقاط يستحيل على فريق كرة قدم أن يحصل عليه بالضبط، باستعمال ركلات المرمى بثلاث نقاط (field goals) ونقاط الهبوط بسبع نقاط (touchdowns) فقط (تجاهل ركلات الأمان، والنقاط الإضافية الضائعة، والتحويلات إلى نقطتين). اثبت صحّة إجابتك بالاستدلال الرياضي.

تلميح. يستحيل تسجيل 11 نقطة بالضبط. فهل يمكنك إثبات أنّه من الممكن تسجيل $n$ نقطة لأيّ $n \ge 12\text{?}$

10.

اثبت أنّ مجموع $n$ مربّعًا يمكن إيجاده على النحو التالي $\begin{equation*} 1^2 +2^2 +3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}\text{.} \end{equation*}$

11.

اثبت أنّ مجموع الزوايا الداخلية لمضلّعٍ محدّب له $n$ ضلعًا يساوي $(n-2)\cdot 180^\circ\text{.}$ (مضلّع محدّب له $n$ ضلعًا هو مضلّعٌ ذو $n$ ضلعًا تكون كل زاويةٍ داخليةٍ فيه أصغر من $180^\circ\text{.}$ )

تلميح. ابدأ بمضلّع $(k+1)$ ، وقسِّمه إلى مضلّع $k$ ومثلّث.

12.

ما الخطأ في «البرهان» التالي للـ«حقيقة» إنّ $n+3 = n+7$ لكل قيم $n$ (بعيدًا عن كون الشيء الذي يزعم إثباته خاطئًا بطبيعة الحال)؟

البرهان.

دع $P(n)$ تكون العبارة $n + 3 = n + 7\text{.}$ وسنُثبت أنّ $P(n)$ صادقة لكل $n \in \N\text{.}$ افترض، لأجل الاستدلال، أنّ $P(k)$ صادقة. أي إنّ $k+3 = k+7\text{.}$ ويجب أن نُظهر أنّ $P(k+1)$ صادقة. والآن بما أنّ $k + 3 = k + 7\text{,}$ أضف 1 إلى الطرفين. فينتج $k + 3 + 1 = k + 7 + 1\text{.}$ وبإعادة التجميع $(k+1) + 3 = (k+1) + 7\text{.}$ لكنّ هذا ببساطة هو $P(k+1)\text{.}$ إذن بمبدأ الاستدلال الرياضي تكون $P(n)$ صادقة لكل $n \in \N\text{.}$

13.

البرهان في المسألة السابقة لا يعمل. لكن إن عدّلنا «الحقيقة» أمكننا أن نحصل على برهانٍ يعمل. اثبت أنّ $n + 3 \lt n + 7$ لكل قيم $n \in \N\text{.}$ ويمكنك أن تقوم بهذا البرهان بالجبر (من دون استدلال)، لكنّ هدف هذا التمرين هو كتابة برهانِ استدلالٍ صحيح.

14.

أوجد الخلل في «البرهان» التالي للـ«حقيقة» إنّ $n \lt 100$ لكل $n \in \N\text{.}$

البرهان.

دع $P(n)$ تكون العبارة $n \lt 100\text{.}$ وسنُثبت أنّ $P(n)$ صادقة لكل $n \in \N\text{.}$ أوّلًا نُثبت الحالة الأساسية: عندما $n = 0\text{,}$ تكون $P(n)$ صادقة، لأنّ $0 \lt 100\text{.}$ والآن في خطوة الاستدلال، افترض أنّ $P(k)$ صادقة. أي إنّ $k \lt 100\text{.}$ والآن إذا كان $k \lt 100\text{,}$ فإنّ $k$ عددٌ ما، مثل 80. وبالطبع $80+1 = 81$ وهو ما زال أصغر من 100. إذن $k +1 \lt 100$ أيضًا. لكنّ هذا هو ما تدّعيه $P(k+1)\,،$ إذن فقد بيّنا أنّ $P(k) \imp P(k+1)\text{.}$ ومن ثمّ، بمبدأ الاستدلال الرياضي، تكون $P(n)$ صادقة لكل $n \in \N\text{.}$

15.

مع أنّ البرهان أعلاه لا يعمل (ول.good أن لا يعمل، فالعبارة التي يحاول إثباتها خاطئة!) يمكننا إثبات شيءٍ مشابه. اثبت أنّ ثمّة متتالية $a_1, a_2, a_3, \ldots$ من الأعداد (لا يلزم أن تكون أعدادًا صحيحة) متزايدة تمامًا بحيث $a_n \lt 100$ لكل $n \in \N\text{.}$ (وبالتزايدة التامّة نعني $a_n \lt a_{n+1}$ لكل $n\text{.}$ فكلّ حدٍّ يجب أن يكون أكبر من سابقه.)

تلميح. في خطوة الاستدلال يمكنك أن تفترض أنّ لديك متتالية متزايدة تمامًا حتى $a_k$ حيث $a_k \lt 100\text{.}$ والآن عليك مجرّد أن تجد الحدّ التالي $a_{k+1}$ بحيث $a_{k} \lt a_{k+1} \lt 100\text{.}$ فما الذي ينبغي أن يكون عليه $a_{k+1}$ ؟

16.

ما الخطأ في «البرهان» التالي للـ«حقيقة» أنّه لكل $n \in \N\text{,}$ يكون العدد $n^2 + n$ فرديًّا؟

البرهان.

دع $P(n)$ تكون العبارة « $n^2 + n$ فرديّ». وسنُثبت أنّ $P(n)$ صادقة لكل $n \in \N\text{.}$ افترض، لأجل الاستدلال، أنّ $P(k)$ صادقة، أي أنّ $k^2 + k$ فرديّ. والآن تأمّل العبارة $P(k+1)\text{.}$ والآن $(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2\text{.}$ وبفرضية الاستقراء يكون $k^2 + k$ فرديًّا، وبالطبع يكون $2k + 2$ زوجيًّا. ومجموع عددٍ فرديّ وعددٍ زوجي يكون دائمًا فرديًّا، إذن $(k+1)^2 + (k+1)$ فرديّ. إذن بمبدأ الاستدلال الرياضي تكون $P(n)$ صادقة لكل $n \in \N\text{.}$

17.

والآن قدّم برهانًا صحيحًا (بالاستدلال، وإن كنت تستطيع ربما إثباته من دون استعمال الاستدلال) للعبارة: «لكل $n \in \N\text{,}$ العدد $n^2 + n$ زوجيّ».

تلميح. في الحالة الاستقرائية ستحتاج إلى إظهار أنّ $(k+1)^2 + (k+1)$ زوجيّ. حلِّل هذا العامل، وحدّد الجزء الذي هو $k^2 + k\text{.}$ فما الذي افترضته عن هذه المقدار؟

18.

اثبت أنّ ثمّة متتالية $a_0, a_1, a_2, \ldots$ من الأعداد الحقيقية الموجبة بحيث يكون المجموع الجزئي $a_0 + a_1 + a_2 + \cdots + a_n$ أصغر تمامًا من $2$ لكل $n \in \N\text{.}$ تلميح: فكّر في كيفية تعريف $a_{k+1}$ بحيث تشتغل حجّة الاستدلال.

تلميح. هذا مشابه لـ التمرين 15، وإن كنت هناك تُظهر أنّ متتاليةً لها كلّ حدودها أصغر من قيمةٍ ما، وهنا تُظهر أنّ المجموع أصغر من قيمةٍ ما. لكنّ المجاميع الجزئية تشكّل متتالية، فالأمر في الواقع متشابه جدًّا.

19.

استعمل الاستدلال لإثبات أنّه إذا صافح $n$ من الأشخاص بعضهم بعضًا، فإنّ العدد الإجمالي للمصافحات هو $\frac{n(n-1)}{2}\text{.}$

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

والسؤال الذي عليك الإجابة عنه لإكمال خطوة الاستدلال هو: كم مصافحةً جديدة تحدث عندما يدخل شخصٌ رقم $k+1$ الغرفة؟ ولماذا تعطيك إضافته الصيغة الصحيحة؟

20.

استعمل الاستدلال لإثبات أنّ $\d\sum_{k=0}^n {n \choose k} = 2^n\text{.}$ أي إنّ مجموع الصفّ رقم $n$ في مثلّث باسكال يساوي $2^n\text{.}$

تلميح. إليك الفكرة: بما أنّ كلّ مدخلٍ في مثلّث باسكال هو مجموع المدخلين فوقه، يمكننا الحصول على الصفّ رقم $k+1$ بجمع كلّ أزواج المداخل من الصفّ رقم $k$ . لكنّ فعل ذلك يستعمل كلّ مدخلٍ في الصفّ رقم $k$ مرّتين. إذن كلّما نزلنا إلى الصفّ التالي ضاعفنا المجموع. وبالطبع فإنّ مجموع الصفّ 0 هو $1 = 2^0$ (وهي الحالة الأساسية). والآن حاول أن تجعل هذا دقيقًا في برهان استدلالٍ رسمي. وستستعمل في الحالة الاستقرائية الحقيقة ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$ .

21.

استعمل الاستدلال لإثبات ${4 \choose 0} + {5 \choose 1} + {6 \choose 2} + \cdots + {4+n \choose n} = {5+n \choose n}\text{.}$ (وهذا مثالٌ على مبرهنة عصا الهوكي (hockey stick theorem).)

تلميح. لترى لماذا يعمل هذا، جرّبه على نسخةٍ من مثلّث باسكال. إنّنا نجمع المداخل فوق قطرٍ، ابتداءً من 1 في الطرف الأيسر من الصفّ الرابع. لنفترض أنّنا جمعنا أوّل 5 مداخل على هذا القطر. فالدعوى أنّ المجموع هو المدخل الواقع أسفل آخر هذه المداخل الخمسة وإلى يساره. ولاحظ أنّه إن كانت هذه صحيحة، وجمعنا بدلًا من ذلك أوّل 6 مداخل، فسنحتاج إلى إضافة المدخل الواقع مرّةً واحدةً إلى يمين المجموع السابق. لكنّ هذين معًا يعطيان المدخل الواقع أسفلهما، وهو أسفل آخر المداخل الستّة على القطر وإلى يسارها. إن تتبّعت ذلك، لترى ما يحدث. لكنه ليس برهانًا جيّدًا. فنحتاج إلى برهان استدلالٍ رسمي.

22.

استعمل قاعدة ضرب اللوغاريتمات ( $\log(ab) = \log(a) + \log(b)$ ) لإثبات، بالاستدلال على $n\text{,}$ أنّ $\log(a^n) = n \log(a)\text{,}$ لكل الأعداد الطبيعية $n \ge 2\text{.}$

23.

لتكن $f_1, f_2,\ldots, f_n$ دوالّ قابلة للاشتقاق. اثبت، باستعمال الاستدلال، أنّ $\begin{equation*} (f_1 + f_2 + \cdots + f_n)' = f_1' + f_2' + \cdots + f_n'\text{.} \end{equation*}$

ويجوز لك أن تفترض أنّ $(f+g)' = f' + g'$ لأيّ دالتين قابلتين للاشتقاق $f$ و $g\text{.}$

تلميح. يُسمح لك بافتراض الحالة الأساسية. أمّا في الحالة الاستقرائية، فاجمع كلّ الدوالّ ما عدا الأخيرة في مجموعةٍ واحدة regarded as مجموع دوالّ، ثمّ طبّق قاعدة مجموع المشتقّات المعتادة، ثمّ فرضية الاستقراء.

24.

افترض أنّ $f_1, f_2, \ldots, f_n$ دوالّ قابلة للاشتقاق. استعمل الاستدلال الرياضي لإثبات قاعدة الضرب المعمَّمة: $\begin{equation*} (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 + f_1 f_2 f_3' \cdots f_n + \cdots + f_1 f_2 f_3 \cdots f_n'\text{.} \end{equation*}$

ويجوز لك أن تفترض أنّ قاعدة الضرب لدالتين صحيحة.

تلميح. في خطوة الاستدلال، نعرف من قاعدة الضرب لدالتين أنّ $\begin{equation*} (f_1f_2f_3 \cdots f_k f_{k+1})' = (f_1f_2f_3\cdots f_k)'f_{k+1} + (f_1f_2f_3\cdots f_k)f_{k+1}'\text{.} \end{equation*}$

ثمّ استعمل فرضية الاستقراء على الحدّ الأول، ووزّع.

25.

في التمارين أثبتنا أنّ قاعدة الاستدلال التالية صحيحة:

	$P \imp Q$
	$Q \imp R$
$\therefore$	$P \imp R$

والآن استعمل الاستدلال الرياضي لإثبات أنّه يمكنك ربط أيّ عددٍ من العبارات من هذا النوع. أي، اثبت أنّه لأيّ $n$ تكون قاعدة الاستدلال التالية صحيحة:

	$P_1 \imp P_2$
	$P_2 \imp P_3$
	$\vdots$
	$P_{n-1} \imp P_n$
$\therefore$	$P_1 \imp P_n\text{.}$

تلميح. يمكنك أن تفترض استقرائيًّا أنّه من أوّل $n-2$ لواحق تستطيع استنتاج $P_1 \imp P_{n-1}\text{.}$ ثمّ يمكنك استعمال جدول حقيقة للتحقّق من أنّ قاعدة الاستدلال هذه المبسّطة صحيحة.

السابق المتتاليات الأسية التالي الاستدلال القوي