البرهان بالاستقراء الرياضي
مُقدَّم| English | المعنى |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | عدد صحيح موجب |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | الاستقراء الرياضي |
| base case/beɪs keɪs/ | الحالة الأساسية |
| inductive step/ɪnˈdʌktɪv step/ | خطوة الاستقراء |
| conjecture/kənˈdʒektʃə/ | فرضية |
| divisible/dɪˈvɪzɪbl/ | قابل للقسمة |
برهان الدومينو
- كيف تثبت أن شيئاً ما صحيح لـ كل عدد صحيح موجب — أي عدد لا نهائي من الحالات؟
- الاستدلال الرياضي يعمل مثل قطع الدومينو: انهدم الأولى (الحالة الأساسية)، وأظهر أن كل قطعة تنهدم التالية (الخطوة الاستدلالية). إذا نجح الاثنان، تنهدم جميعها.
طريق البرهان بالاستقراء الرياضي
اعتبر الاستقراء كدرع أولي واحد بالإضافة إلى قاعدة تدفع كل حالة تالية.
خطوتان للاستدلال الرياضي
- الاستدلال الرياضي يثبت نتيجة لكل عدد صحيح موجب $n$ في خطوتين:
- الحالة الأساسية: إثبات صحته لـ $n = 1$.
- الخطوة الاستدلالية: افترض أنها صحيحة لـ $n = k$، ثم أثبت أنها صحيحة لـ $n = k + 1$.
مثال محلول. أثبت $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. الحالة الأساسية ($n=1$): الطرف الأيسر $= 1$، الطرف الأيمن $= \dfrac{1(2)}{2} = 1$. ✓ الخطوة الاستدلالية: افترض صحة $n = k$. بالنسبة لـ $n = k+1$: $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$. ✓
إثبات بالاستدلال الرياضي يعمل كسلسلة من قطع الدومينو التي تنهدم
خطوات البرهان بالاستقراء الرياضي هما الحالة الأساسية و:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
يحتاج الاستقراء إلى حالة أساسية بالإضافة إلى خطوة استقرائية من k إلى k+1.
عادةً ما تُظهر الحالة الأساسية أن النتيجة صحيحة لـ:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
تتحقق الحالة الأساسية من أصغر قيمة، عادةً n = 1.
إذا تحققت كل من الحالة الأساسية والخطوة الاستقرائية، تكون النتيجة صحيحة لجميع الأعداد الصحيحة الموجبة n.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
هذا بالضبط ما يضمنه مبدأ الاستقراء.
لماذا كلا الخطوتين ضروريان
- الحالة الأساسية تبدأ السلسلة. بدونها، يمكنك "إثبات" عبارات خاطئة.
- الخطوة الاستدلالية تمدها. بدونها، لم تثبت سوى حالة واحدة.
كلا الخطوتين ضروريتان. برهان بخطوة استدلالية فقط يشبه صف دومينو لم يدفعه أحد — لن يبدأون بالانهيار أبداً. وبرهان بالحالة الأساسية فقط يشبه دفع قطعة واحدة — ستسقط واحدة فقط.
يمكنك إثبات نتيجة بالاستقراء باستخدام الخطوة الاستقرائية فقط، بدون حالة أساسية.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
كلا الخطوتين ضروريتان. بدون الحالة الأساسية، لا تبدأ السلسلة أبداً.
تخمين ثم إثبات
- غالباً ما تضع تخميناً (توقعاً منطقياً) من بضعة حالات، ثم تتأكد منه عبر إثبات استدلالي.
- مثال: $1 + 3 + 5 + 7 = 16 = 4^2$. التخمين: مجموع أول $n$ أعداد فردية هو $n^2$.
باستخدام الاستقراء، مجموع 1 + 2 + ... + n = n(n+1)/2. بالنسبة لـ n = 10، أوجد المجموع.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
10(11)/2 = 55.
الاستدلال للقابلية للقسمة
- أثبت أن $3^n - 1$ يقبل القسمة على $2$ لجميع الأعداد الصحيحة الموجبة $n$.
- الحالة الأساسية ($n=1$): $3^1 - 1 = 2$، يقبل القسمة على $2$. ✓
- الخطوة الاستدلالية: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. بما أن $3^k - 1$ يقبل القسمة على $2$ (بافتراض), فإن التعبير بأكمله يقبل القسمة أيضاً. ✓
في الرياضيات، الفرضية هي:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
الفرضية عبارة عن عبارة غير مثبتة مبنية على أدلة — حاول بعدها إثباتها (غالباً بالاستقراء).
لقد فهمت الأمر
- التراجع = الحالة الأساسية ($n=1$) + الخطوة الاستنتاجية ($n=k \Rightarrow n=k+1$)
- الخطوتان معاً تثبتان ذلك لـ جميع الأعداد الصحيحة الموجبة
- غالباً تخمين من الحالات، ثم إثبات بالاستدلال