الاستقراء القوي: الفرض وأمثلة على التحليل والمتتاليات

العبارة والمجال يأتيان قبل الفرض

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

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

في المثال الأول سنثبت أن كل عدد صحيح n ≥ 2 يمكن كتابته حاصل ضرب أعداد أولية. وفي المثال الثاني سنثبت حدًا لمتتالية عند n ≥ 1. اختلاف المجال يفسر اختلاف البداية قبل أي حساب. كما أن عبارة عن فهارس صحيحة لا تتحول إلى عبارة عن جميع الأعداد الحقيقية لمجرد أن الصيغة التي تظهر فيها يمكن حسابها لبعض القيم الكسرية.

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

الفرق في الفرض: حالة واحدة أم المجال السابق كله؟

في الاستقراء القوي، تثبت البداية، ثم تفترض صحة العبارة لجميع الفهارس السابقة في مجالها حتى k، وتثبت الحالة k + 1. يتيح الفرض استعمال حالة أقدم من السابقة مباشرة؛ والبداية تتبع المجال المحدد. [1] [2] [4]

عند كتابة الانتقال من k إلى k + 1 في مثال يبدأ عند واحد، يكون الفرض القوي هو صحة P(1), P(2), …, P(k). إذا احتجت إلى الحالة الثالثة أو إلى الحالة ذات الفهرس k − 1، فيمكنك استعمالها متى كان فهرسها داخل هذا المجال. لا تكتف بكتابة «نفترض أنها صحيحة» من دون بيان ما تعود عليه كلمة «أنها».

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

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

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

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

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

لنثبت حالة عدد N > 2 بعد افتراض الادعاء لجميع الأعداد من اثنين إلى N − 1. نحتاج إلى مناقشة احتمالين يغطيان العدد: أن يكون أوليًا، أو أن يكون مركبًا. لن تكون قسمة كل عدد على سلفه مباشرة هي الخطوة المناسبة؛ لهذا يتيح الفرض الأوسع صورة أوضح للحجة.

حالة المركب: لماذا يدخل العاملان في مجال الفرض؟

إذا كان العدد N أوليًا، فهو حاصل ضرب بعامل واحد وتنتهي هذه الحالة. وإذا كان مركبًا، يوجد عددان صحيحان r, s أكبر من واحد بحيث N = rs. كل منهما أصغر من N، لأن العامل الآخر لا يقل عن اثنين: r = N/s ≤ N/2 < N، والعلاقة المقابلة صحيحة للعامل الثاني.

إذن يقع العاملان بين اثنين وN − 1، فيشملهما الفرض القوي. لكل عامل حاصل ضرب من أوليات يساويه؛ ضرب القائمتين معًا يعطي حاصل ضرب من أوليات يساوي rs = N. ليست هناك حاجة إلى أن يكون العاملان اللذان وجدتهما أوليين أصلًا، لأن دور الفرض هو توفير التحليل لهما.

وهنا يظهر الفرق العملي في كتابة الفرض. معرفة الادعاء للعدد N − 1 وحده لا تعرض لك مباشرة تحليل العاملين اللذين اخترتهما، فقد يكون أحدهما صغيرًا جدًا. الفرض الذي يغطي جميع الأعداد الأصغر يطابق ما تستعمله الحجة بالفعل. هذا لا يعني استحالة كتابة برهان معتاد مكافئ؛ سنوضح طريقة جمع الحالات في عبارة واحدة لاحقًا.

قراءة البرهان في العدد أربعة وثمانين

خذ العدد 84 وافصله في مثالنا إلى 6 × 14. العاملان أصغر من أربعة وثمانين وأكبر من واحد، فيدخلان في مجال فرض خطوة هذا العدد. التحليلان 6 = 2 × 3 و14 = 2 × 7 يجتمعان في 84 = 2 × 2 × 3 × 7. المثال يوضح موقع استعمال حالتين سابقتين غير متجاورتين مع العدد الحالي.

يمكن أن تختار تفكيكًا آخر، مثل 12 × 7، وتستخدم تحليل اثني عشر إلى 2 × 2 × 3 مع الأولية للعدد سبعة. نجاح المسارين العدديين لا يضيف وحدانية إلى ما أثبته البرهان العام هنا؛ فهو يثبت أن طريقًا إلى حاصل ضرب من أوليات موجود. المقارنة بين كل التحليلات الممكنة تحتاج إلى حجة أخرى.

وعند استعمال العامل نفسه مرتين، كما في 100 = 10 × 10، تستطيع استعمال الحالة السابقة نفسها مرتين أيضًا. لا يشترط الفرض أن يكون العاملان مختلفين، ولا يمنع تكرار أولي في حاصل الضرب. في هذا المثال نحصل على 2 × 5 × 2 × 5. القاعدة التي نراجعها هي أن الفهرس المستخدم أصغر من الفهرس الحالي وداخل المجال، لا أن كل حالة تستخدم مرة واحدة فقط.

مثال ثانٍ: متتالية تعتمد على حدين سابقين

نعرّف متتالية تعليمية بـ a₁ = 2 وa₂ = 3، وللفهارس n ≥ 3 نضع aₙ = aₙ₋₁ + aₙ₋₂. أول القيم هي اثنان وثلاثة وخمسة وثمانية وثلاثة عشر وواحد وعشرون وأربعة وثلاثون. التعريف يحدد الحدين الأولين قبل بدء العلاقة المتكررة، فلا نحاول استعمال حد ذي فهرس صفر لإنشاء الحد الثاني.

ادعاؤنا هو aₙ ≤ 2ⁿ لجميع الفهارس الصحيحة التي لا تقل عن واحد. نقارن القيم الأولى بالقوى: اثنان مقابل اثنين، وثلاثة مقابل أربعة، وخمسة مقابل ثمانية، وثمانية مقابل ستة عشر. هذه القيم تجعل الادعاء معقولًا للفحص الأولي، لكننا لا نستنتج منها صحة المقارنة لجميع الفهارس.

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

البدايتان ثم خطوة الحد الأعلى

عند الفهرس الأول، a₁ = 2 = 2¹، فتتحقق المقارنة. وعند الثاني، a₂ = 3 ≤ 4 = 2². نفترض بعد ذلك صحة الادعاء من واحد حتى k، حيث k ≥ 2، ونريد إثباته عند k + 1. هذا القيد يجعل الفهرس k − 1 واحدًا على الأقل، ويدخله مع k في مجال الفرض.

من التعريف، aₖ₊₁ = aₖ + aₖ₋₁. وباستعمال الفرض مرتين، نحصل على aₖ₊₁ ≤ 2ᵏ + 2ᵏ⁻¹ = 3 × 2ᵏ⁻¹. بما أن القوة موجبة وثلاثة أقل من أربعة، فإن هذا المقدار لا يتجاوز 4 × 2ᵏ⁻¹ = 2ᵏ⁺¹. وصلنا إلى المقارنة المطلوبة عند الفهرس الجديد.

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

لماذا لا يكفي تحديد الحد الأول وحده؟

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

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

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

كلمة قوي لا تعني قوة منطقية أكبر

الاستقراء القوي والمعتاد متكافئان من حيث قوة الإثبات في هذا السياق. كلمة «قوي» تشير إلى اتساع فرض الخطوة، ولا تعني أنه يثبت عبارات يستحيل إثباتها بالاستقراء المعتاد. [1] [3]

يمكن أن نعرّف عبارة جديدة Q(k) تقول إن P(j) صحيحة لكل فهرس j من بداية المجال حتى k. عندما نثبت Q(k + 1) بعد فرض Q(k)، تكون الحالات القديمة محفوظة في الفرض، ويكفي إضافة الحالة الجديدة التي تنتجها حجة الاستقراء القوي. أصبح الانتقال معتادًا على العبارة المجمّعة بدل العبارة المفردة. [3]

للبداية عند اثنين مثلًا، العبارة Q(2) هي صحة P(2)، والانتقال يضيف P(3) ثم ما بعدها مع الاحتفاظ بكل ما سبق. هذه إعادة تنظيم للفرض، لا برهان جديد يوسع الادعاء. قد تكون صياغة الاستقراء القوي أقصر وأسهل قراءة عندما تتعامل الحجة مع أكثر من فهرس سابق أو مع عاملين غير متجاورين.

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

أخطاء في المجال وفي الحالة الجديدة

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

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

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

جدول القيم فحص مساعد وليس برهانًا

في متتاليتنا، قيم الفهارس من واحد إلى سبعة هي 2, 3, 5, 8, 13, 21, 34، والقوى المقابلة 2, 4, 8, 16, 32, 64, 128. وتوضح الحالة السابعة استعمال الخامسة والسادسة: ثلاثة عشر زائد واحد وعشرين يساوي أربعة وثلاثين. الجدول يساعدك على معرفة ما تمثله الرموز، لكنه لا يتضمن جميع الفهارس التي يشملها الادعاء.

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

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

اختيار المتغير الذي يتناقص في الحجة

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

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

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

ورقة مراجعة لبرهان الاستقراء القوي

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

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

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