الاستقراء القوي: خمس بدايات لتكوين المجاميع من5 و8

حدد الادعاء وعدد المجموعات

الاستقراء العادي يربطP(k) بـP(k+1) مع بداية صحيحة؛ القوي يتيح جميع الحالات السابقة. [1][2]

نعرفP(n) بوجود عددين صحيحين غير سالبينa وb يحققان n=5a+8b. العددa يحصي مجموعات5، والعددb مجموعات8. المطلوب كل عدد صحيحn≥28، مع إمكان تكرار المجموعات دون حد.

مثال29: مجموعة واحدة من5 وثلاث من8، لأن5+24=29. ومثال30: ست مجموعات من5 وصفر من8. صفر مجموعة يختلف عن مجموعة ذات حجم صفر؛ الحجم المسموح5 أو8.

إذا كان مخزون المجموعات محدودًا، لا يكفي هذا النموذج. مثلًا مع مجموعة واحدة من كل حجم لا تتاح إلا المجاميع0،5،8،13؛ العدد29 خارج هذه القائمة.

خمس بدايات صحيحة

الحالات الأساسية تسبق خطوة الاستقراء؛ عددها يتبع اعتماد الخطوة على الحالات السابقة. [1]

نحسب28=5×4+8×1؛29=5×1+8×3؛30=5×6+8×0؛31=5×3+8×2؛32=5×0+8×4. كلها تستخدم عدد مجموعات صحيحًا غير سالب.

لو اكتفينا بـ28 ثم أضفنا5 مرارًا، حصلنا على28،33،38،43… دون29. هذه السلسلة تحافظ على الباقي3 عند القسمة على5.

حتى البدايات28 إلى31 لا تكفي لهذه الخطوة: عند محاولة32، نحتاج32−5=27، وسيظهر أنه غير ممكن. لذلك أدرجنا32 نفسه بداية، لا نتيجة زائفة للفرض.

استخدم الفرض داخل مجاله

نفترضP(j) لكل28≤j<n، حيثn≥33. عندئذ28≤n−5<n، فالحالةn−5 مشمولة بالفرض. [1]

نكتب n−5=5a+8b بأعداد مجموعات غير سالبة. بإضافة مجموعة5 نحصل على n=5(a+1)+8b؛ تبقىa+1 وb صحيحين غير سالبين. مع البدايات تثبت النتيجة لكلn≥28. [1]

عند33 نرجع إلى تمثيل28 بالزوج(4,1)، ثم يصبح الزوج(5,1):25+8=33. وعند34 نرجع إلى تمثيل29 بالزوج(1,3)، فنحصل على(2,3):10+24=34.

وعند42 نرجع إلى تمثيل37 بالزوج(1,4)، ثم(2,4) يعطي10+32=42. لا نطرح من عدد مجموعات8 ولا نستبدل الحجمين؛ نزيد عدد مجموعات5 بواحد.

معنى «القوي» فرض أوسع؛ وهو متكافئ مع الاستقراء العادي، ويمكن تجميع الحالات السابقة في عبارة واحدة. [3]

لماذا يتوقف الادعاء عند28؟

لو كان27=5a+8b معa وb غير سالبين، لكان8b≤27؛ لذلكb من0 إلى3 فقط. البواقي المطلوبة5a هي27،19،11،3؛ بواقيها عند القسمة على5 هي2،4،1،3، وكلها غير صفر.

إذا سمحنا بعدد مجموعات سالب وجدنا27=5×7+8×(−1). المساواة صحيحة، لكنها ليست تمثيلًا مسموحًا في المسألة. استبعاد السالب جزء من النموذج، لا تصحيح لعملية الضرب.

البرهان السابق يعطي جميع المجاميع من28 فصاعدًا، وفحص27 يمنع تخفيض بداية الادعاء الشامل إلى27. لا يعني ذلك أن كل عدد أقل من28 مستحيل:26=5×2+8×2، و25=5×5.

راجع خمس البدايات، ثم حدn≥33 ووقوعn−5 داخل الفرض، وأخيرًا عدم سلبية عدد المجموعات. الحسابات المحدودة تراجع الأمثلة؛ الخطوة العامة تغطي المجاميع الأكبر.