الاستدلال القوي

القسم 4.6 الاستدلال القوي

الأهداف

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

1. أن تشرح الفرق بين البرهان بالاستدلال والبرهان بالاستدلال القوي (strong induction).
2. أن تستعمل الاستدلال القوي لإثبات العبارات.

معاينة القسم

استكشف!

ابدأ بمربّع من الورق. تريد أن تقطع هذا المربّع إلى مربّعات أصغر، دون أيّ هدر (كلّ قطعةِ ورقٍ تنتهي إليها يجب أن تكون مربّعًا). من البديهي أنّه ممكن تقسيم المربّع إلى 4 مربّعات. ويمكنك أيضًا تقطيعه إلى 9 مربّعات. ويتبيّن أنّه ممكن تقسيم المربّع إلى 7 مربّعات (مع أنّها ليست جميعها بالحجم نفسه). فما الأعداد الأخرى من المربّعات التي يمكن أن تنتهي إليها؟

أحيانًا، لإثبات صحّة $P(k+1)$، يكون من المفيد أن نعرف أنّ $P(k)$ و $P(k-1)$ و $P(k-2)$ جميعها صادقة. وهذا هو الحال بالتأكيد عند إثبات شيءٍ عن علاقةٍ تعاودية معطاة على هيئة مجموعةٍ من حدَّين سابقين.

المثال 4.6.1.

أثبت أنّ $2^n$ حلٌّ للعلاقة التعاودية $a_n = 5a_{n-1} - 6a_{n-2}$ مع الشروط الابتدائية $a_0 = 1$ و$a_1 = 2\text{.}$

الحلّ.

البرهان.

دع $P(n)$ هي العبارة، «$a_n = 2^n\text{.}$» وسنُبيّن أنّ هذه العبارة صادقة لكل $n \ge 0\text{.}$

الحالات الأساسية: $a_0 = 2^0 = 1$ و$a_1 = 2^1 = 2$ كلتاهما توافق الشروطَ الابتدائية.

الحالة الاستقرائية: لتكن $k \ge 2$ اعتباطيّة. افترض أنّ $P(k)$ و$P(k-1)$ صادقتان معًا. أي، افترض أنّ $a_k = 2^k$ و$a_{k-1} = 2^{k-1}\text{.}$ وسنُبيّن أنّ $P(k+1)$ صادقة. تأمّل $a_{k+1}\text{.}$ لدينا $$\begin{align*} a_{k+1} = \amp 5a_k - 6a_{k-1}\\ = \amp 5\cdot 2^k - 6\cdot 2^{k-1}\\ = \amp 10 \cdot 2^{k-1} - 6 \cdot 2^{k-1}\\ = \amp 4\cdot 2^{k-1}\\ = \amp 2^{k+1}\text{.} \end{align*}$$ إذن، بمبدأ الاستدلال الرياضي، تكون العبارة $P(n)$ صادقة لكل $n \ge 0\text{.}$

حسنًا، أو بالأحرى مبدأ الاستدلال الرياضي. فهل ما فعلناه جيّد؟

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

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

1.

نشاط فكّر في اللغز التالي:

لديك شريطٌ من الشوكولاتة مستطيل، مكوّن من $n$ مربّع شوكولاتةٍ متطابقة. يمكنك أن تأخذ هذا الشريط وتكسره على امتداد أيّ صفٍّ أو عمود. كم مرّةً ستحتاج إلى كسر الشريط لتقليله إلى $n$ مربّع شوكولاتة منفرد؟

أوّلًا، قد يبدو هذا السؤال مستحيلًا. ربّما كنا نقصد السؤال عن أصغر عددٍ من الكسرات اللازم. لنبحث في الأمر.

(a)

افترض أنّك بدأت بشريط $1\times 3$. كم كسرةً ستحتاج إليه لتقليله إلى مربّعات منفردة؟

(b)

ولو كان لديك شريط $1\times 4$، فكم كسرةً مطلوبة؟

ولو كانت لديك 4 مربّعات مرتّبة في مربّع $2\times 2$، فإنّ كسرتك الأولى ستقتضي أن تكسر الشوكولاتة إلى شريطين $1 \times 2$. ثمّ سيحتاج كلٌّ من هذين الشريطين إلى مزيدٍ من الكسرات، بمجموعٍ كسراتٍ للانتقال من $2\times 2$ إلى المربّعات المنفردة.

(c)

يمكن أن يكون شريط $6$ مربّعاتٍ إمّا شريط $1 \times 6$، فيتطلّب كسرات، أو شريط $2 \times 3$.

وهناك طريقتان للمضيّ قدمًا الآن.

1. اكسر الشريط إلى شريطين $1 \times 3$، كلٌّ منهما يتطلّب مزيدًا من الكسرات، بمجموعٍ كسرات.
2. اكسر الشريط إلى شريط $1\times 2$ وشريط $2 \times 2$. يتطلّب الشريط $1 \times 2$ مزيدًا من الكسرات، ويتطلّب الشريط $2 \times 2$ مزيدًا من الكسرات، بمجموعٍ كسرات.

(d)

استنادًا إلى البيانات أعلاه، ما الذي ينبغي أن يكون تخميننا لعدد الكسرات اللازم لتقليل شريطٍ من $n$ مربّعًا إلى مربّعات منفردة، بدلالة $n\text{?}$

ستستغرق كسراتٍ لتقليل شريطٍ من $n$ مربّعًا إلى مربّعات منفردة.

(e)

هل نصدّق هذا؟ افترض أنّك استخدمت كسرةً واحدةً لتقليل الشريط إلى شريطين أصغر، كلٌّ فيهما $a$ و$b$ مربّعًا. فإنّ كان التخمين صحيحًا، فكم كسرةً إضافية ستحتاج إليها لتقليل الشريط ذي الحجم $a$؟

وكم كسرةً إضافية ستحتاج إليها لتقليل الشريط ذي الحجم $b$؟

وكم كسرةً يكون ذلك كلّه معًا، بدلالة $a$ و$b\text{,}$ بما في ذلك الكسرة الأولى؟

لكنّ ما هو $a+b\text{?}$ لقد حصلنا على $a$ و$b$ بكسر المربّعات الـ $n$ إلى قطعتين، إذن $a+b =$. وهذا يعطينا عددًا إجماليًّا من الكسرات مقداره .

قسم فرعي: القسمة والتغلب

تخيَّل التعريفات التعاودية بوصفها تعليماتٍ لبناء سُلّم. يمكنك بناء السلم بارتفاعٍ ما شئت، لأنّ لديك تعليمات لبناء العتبة التالية، ما دمت واقفًا على العتبة التي قبلها.

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

وبعبارةٍ أدقّ، افترض أنّك تحاول إثبات أنّك تستطيع الوصول إلى العتبة 4 من السلم. لقد أثبتَّ بنجاح أنّه بإمكانك الوصول إلى العتبة 1، وأنّه من أيّ عتبةٍ تستطيع الوصول إلى التي تليها. إذن تستطيع الوصول إلى العتبة 1، ومن 1 تستطيع الوصول إلى 2. ومن 2 تستطيع الوصول إلى 3، ومن 3 تستطيع الوصول إلى 4. إذن تستطيع الوصول إلى 4.

لكن لاحظ أنّك على طول الطريق تعرف أنّك مررتَ بالعتبات من 1 إلى 3. ثمّ إنّه لا بأس من أن نفترض أنّنا مررنا بكلّ العتبات التي تحت العتبة التالية التي نحاول الوصول إليها. وهذه هي الفكرة التي يقوم عليها الاستدلال القوي.

واستعارةُ السُلَّم الأفضل للاستدلال القوي هي أن نفكّر في السلاسل بوصفها أشياءً يمكننا تكديسها فوق بعضها بعض. نريد أن نبيّن أنّه من الممكن تسلّق 20 عتبةٍ من سُلَم. فلنقسم ذلك إلى سُلَّمين أصغر، لنقل سُلَمًا بـ 12 عتبةً وسُلَمًا بـ 8 عتبات. يمكننا أن نفترض أنّنا نستطيع تسلّق كليهما، لأنّ 20 أصغرُ حجمٍ لم نتحقّق منه بعد. حسنًا، ضع هذين السلمين معًا، فتحصل على $12+8 = 20$ عتبة.

من الأفضل ألّا ننزل عن استعارتنا الهشّة قبل أن نؤذي أنفسنا. فلننظر إلى تعريفٍ رسميّ للاستدلال القوي.

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

ابدأ بذكر ما نريد إثباته: «دع $P(n)$ تكون العبارة….» ثمّ أثبت حقيقتين:

1. الحالة الأساسية: أثبت أنّ $P(0)$ صادقة. (وربّما أثبت كذلك الحالات الأساسية الأخرى اللازمة.)
2. الحالة الاستقرائية: افترض أنّ $P(j)$ صادقة لكل $j \le k\text{.}$ أثبت أنّ $P(k+1)$ صادقة.

اختُتم بقولك: «إذن، بالاستدلال القوي، تكون العبارة $P(n)$ صادقة لكل $n \gt 0\text{.}$»

وبالطبع، من المقبول استبدال 0 بحالةٍ أساسية أكبر عند الحاجة. 2 تقنيًّا، لا يشترط الاستدلال القوي منك إثبات حالةٍ أساسية منفصلة. ذلك لأنّك عند إثبات الحالة الاستقرائية يجب أن تُبيّن أنّ $P(0)$ صادقة، بافتراض أنّ $P(k)$ صادقة لكل $k \lt 0\text{.}$ لكنّ هذا لا يفيدك في شيء، فتنتهي إلى إثبات $P(0)$ على أيّ حال. ولأجل الاطمئنان، سنُدرج الحالة الأساسية على نحوٍ منفصل دائمًا.

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

مبرهنة 4.6.2.

معطى شريطِ شوكولاتةٍ مستطيلٍ من $n$ مربّعًا، فإنّه يستغرق دائمًا $n-1$ كسرةً لتقليل الشريط إلى مربّعات منفردة.

البرهان.

دع $P(n)$ هي العبارة، «يستغرق شريط شوكولاتةٍ من $n$ مربّعًا $n-1$ كسرةً لتقليله إلى مربّعات منفردة.»

الحالة الأساسية: تأمّل $P(2)\text{.}$ ويجب أن تكون المربّعات مرتّبة في مستطيل $1\times 2$، ونحتاج $2-1 = 1$ كسرةً لتقليله إلى مربّعات منفردة.

الحالة الاستقرائية: ثبّت عددًا $k\ge 2$ اعتباطيًّا وافترض أنّ $P(j)$ صادقة لكل $j \le k\text{.}$ تأمّل شريط شوكولاتةٍ مستطيلٍ من $k+1$ مربّعًا. اكسر الشريط مرّةً واحدةً على امتداد أيّ صفٍّ أو عمود. ينتج عن ذلك شريطَي شوكولاتة، لنقل بحجمي $a$ و$b$ . أي إنّ لدينا شريط شوكولاتةٍ مستطيلٍ من $a$ مربّعًا، وشريط شوكولاتةٍ مستطيلٍ من $b$ مربّعًا، و$a+b = k+1\text{.}$

ونعرف أيضًا أنّ $a \le k$ و$b \le k\text{,}$ إذن بفرضية الاستقراء لدينا، تكون $P(a)$ و$P(b)$ صادقتين. لتقليل الشريط ذي الـ $a$ مربّعًا إلى مربّعات منفردة يلزم $a-1$ كسرة؛ ولتقليل الشريط ذي الـ $b$ مربّعًا إلى مربّعات منفردة يلزم $b-1$ كسرة. وبعمل ذلك ينتج شريطنا الأصليّ مقلَّلًا إلى مربّعات منفردة. ومجتمعةً تتضمّن الكسرةَ الأولى، مع $a-1$ و$b-1$ من الكسرات، أي بمجموعٍ قدره $$\begin{equation*} 1+a-1+b-1 = a+b-1 = k+1 - 1 = k \end{equation*}$$ كسرة. إذن $P(k+1)$ صادقة.

إذن، بالاستدلال القوي، تكون العبارة $P(n)$ صادقة لكل $n \ge 2\text{.}$

وهنا مثالٌ أكثر صلةً بالرياضيات:

المثال 4.6.3.

أثبت أنّ كلّ عددٍ طبيعيّ أكبر من 1 إمّا أوّليّ أو يمكن كتابته على هيئة جداءِ أعدادٍ أوّليّة.

الحلّ. أوّلًا، الفكرة: إن أخذنا عددًا ما $n\text{,}$ فقد يكون أوّليًّا. وإن كان كذلك، فقد فرغنا. وإن لم يكن كذلك، فهو مركّب، أي إنّه جداءُ عددين أصغر منه. وكلُّ عاملٍ من هذين أصغرُ من $n$ (لكنّه 2 على الأقلّ)، فيمكننا تكرار الحجة مع هذين العددين. لقد انتقلنا إلى حالةٍ أصغر.

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

البرهان.

دع $P(n)$ هي العبارة، «$n$ إمّا أوّليّ أو يمكن كتابته على هيئة جداءِ أعدادٍ أوّليّة.» وسنُثبت أنّ $P(n)$ صادقة لكل $n \ge 2\text{.}$

الحالة الأساسية: $P(2)$ صادقة لأنّ $2$ أوّليّ بالفعل.

الحالة الاستقرائية: افترض أنّ $P(j)$ صادقة لكل $j \le k\text{.}$ نريد أن نُبيّن أنّ $P(k+1)$ صادقة. أي، نريد أن نُبيّن أنّ $k+1$ إمّا أوّليّ أو جداءُ أعدادٍ أوّليّة. فإن كان $k+1$ أوّليًّا، فقد فرغنا. وإن لم يكن كذلك، فإنّ لـ $k+1$ أكثرَ من قاسمين، ويمكننا كتابة $k+1 = m_1 \cdot m_2\text{,}$ حيث $m_1$ و$m_2$ أصغرُ من $k+1$ (وأكبرُ من 1). بفرضية الاستقراء، فإنّ $m_1$ و$m_2$ كلًّا منهما إمّا أوّليّ أو يمكن كتابته على هيئة جداءِ أعدادٍ أوّليّة. وفي الحالين، لدينا أنّ $m_1\cdot m_2 = k+1$ يمكن كتابته على هيئة جداءِ أعدادٍ أوّليّة.

إذن، بالاستدلال القوي، تكون العبارة $P(n)$ صادقة لكل $n \ge 2\text{.}$

أمّا استعمالُك الاستدلالَ الاعتياديّ أم الاستدلالَ القوي فيعتمد على العبارة التي تريد إثباتها. فإن أردتَ أن تكون آمنًا، فيمكنك دائمًا استعمال الاستدلال القوي. فهو فعلًا أقوى، إذ يستطيع إنجاز كلّ ما يستطيع إنجازه الاستدلال «الضعيف». لكنّ استعمال الاستدلال الاعتياديّ يكون أسهل في أغلب الأحيان، إذ إنّ هناك موضعًا واحدًا فقط يمكنك فيه استعمال فرضية الاستقراء. وهناك أيضًا ما يُقال عن الأناقة في البراهين. فإن استطعتَ إثبات عبارةٍ بأدواتٍ أبسط، فكان من جيّد أن تفعل ذلك.

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

1.

• صادق.
• هذا معكوس. أنت لا تزال تُثبت الحالة التالية، وإنّما الفرق أنّه يجوز لك افتراض كلّ الحالات السابقة (لا الحالة السابقة وحدها).
• خاطئ.
• هذا معكوس. أنت لا تزال تُثبت الحالة التالية، وإنّما الفرق أنّه يجوز لك افتراض كلّ الحالات السابقة (لا الحالة السابقة وحدها).

2.

أيٌّ ممّا يلي من الادّعاءات عن العلاقة بين البرهان بالاستدلال والبرهان بالاستدلال القوي صحيح؟

• أيّ برهانٍ بالاستدلال يمكن كتابته على هيئة برهانٍ بالاستدلال القوي.
• أيّ برهانٍ بالاستدلال القوي يمكن كتابته على هيئة برهانٍ بالاستدلال.
• الاستدلال القوي «أقوى» لأنّ الحالة الأساسية أقوى.
• الاستدلال القوي «أقوى» لأنّ فرضية الاستقراء أقوى.

3.

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

لتكن \(P(n)\) هي العبارة أنّ لوح شوكولاتة طوله \(n\) مربّعًا يمكن كسره إلى \(n\) قطعة بكسرٍ \(n-1\) مرّات.
---
\(P(1)\) صادقة لأنّ لوح الشوكولاتة الذي طوله مربّع واحد يكون قطعةً واحدة بالفعل.
---
افترض أنّ \(P(j)\) صادقة لكل \(j \le k\) مع \(k \ge 1\) اعتباطيًّا\text{.}
---
ولتأخذ لوح شوكولاتة طوله \(k+1\) مربّعًا.
---
وأيًّا كان الموضع الذي تكسر عنده هذا اللوح، فستحصل على لوحين أصغر، طولاهما \(a\) و\(b\) مثلًا\text{.}
---
ولأنّ كلًّا من \(a\) و\(b\) لا يتجاوز \(k\text{,}\)، الممكن كسر هذين اللوحين الأصغر إلى مربّعاتٍ مفردة باستخدام \(a-1\) و\(b-1\) كسرٍ على التوالي.
---
إذن العدد الإجمالي للكسرات هو \(a-1 + b-1 + 1 = a+b -1\text{,}\) وهو \(k+1-1 = k\text{.}\)
---
إذن، بمبدأ الاستدلال القوي، \(P(n)\) صادقة لكل \(n \ge 1\text{.}\)