مقالات

3.4: الاستقراء الرياضي - مقدمة


يمكن استخدام الاستقراء الرياضي لإثبات أن الهوية صالحة لجميع الأعداد الصحيحة (n geq1 ). فيما يلي مثال نموذجي لمثل هذه الهوية: [1 + 2 + 3 + cdots + n = frac {n (n + 1)} {2}. ] بشكل عام ، يمكننا استخدام الاستقراء الرياضي لإثبات ذلك دالة مقترحة (P (n) ) صحيحة لجميع الأعداد الصحيحة (n geq1 ).

التعريف: الاستقراء الرياضي

لإثبات أن الوظيفة الافتراضية (P (n) ) صحيحة لجميع الأعداد الصحيحة (n geq1 ) ، اتبع الخطوات التالية:

  • الخطوة الأساسية: تحقق من صحة (P (1) ).
  • خطوة استقرائية: أظهر أنه إذا كان (P (k) ) صحيحًا لبعض الأعداد الصحيحة (k geq1 ) ، فإن (P (k + 1) ) يكون صحيحًا أيضًا.

الخطوة الأساسية تسمى أيضًا خطوة المرساة أو ال خطوة أولية. تقنية الإثبات هذه صالحة بسبب النظرية التالية.

النظرية ( PageIndex {1} label {thm: pmi} ): مبدأ الاستقراء الرياضي

إذا (S subseteq mathbb {N} ) هكذا

  • (1 في S ) ، و
  • (ك في S Rightarrow ك + 1 في S ) ،

ثم (S = mathbb {N} ).

ملاحظة

هنا رسم تخطيطي للإثبات. من (i) ، نعلم أن (1 في S ). ثم يتبع من (2) أن (2 في S ). بتطبيق (ii) مرة أخرى ، نجد أن (3 in S ). وبالمثل ، (4 في S ) ، ثم (5 في S ) ، وهكذا. نظرًا لأن هذه الحجة يمكن أن تستمر إلى أجل غير مسمى ، فإننا نجد ذلك (S = mathbb {N} ).

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

على الرغم من أننا لا نستطيع تقديم دليل مرضٍ على مبدأ الاستقراء الرياضي ، إلا أنه يمكننا استخدامه لتبرير صحة الاستقراء الرياضي. لنفترض أن (S ) هو مجموعة الأعداد الصحيحة (n ) التي تكون الوظيفة الافتراضية (P (n) ) صحيحة. تتحقق الخطوة الأساسية للاستقراء الرياضي من (1 في S ). توضح الخطوة الاستقرائية أن (k in S ) يعني (k + 1 in S ). لذلك ، فإن مبدأ الاستقراء الرياضي يثبت ذلك (S = mathbb {N} ). ويترتب على ذلك أن (P (n) ) صحيح لجميع الأعداد الصحيحة (n geq1 ).

تثبت الخطوة الأساسية والخطوة الاستقرائية معًا أن [P (1) Rightarrow P (2) Rightarrow P (3) Rightarrow cdots ،. ] لذلك ، (P (n) ) هو صحيح لجميع الأعداد الصحيحة (n geq1 ). قارن الاستقراء بسقوط قطع الدومينو. عندما يسقط الدومينو الأول ، فإنه يقرع قطعة الدومينو التالية. الدومينو الثاني يقرع بدوره قطعة الدومينو الثالثة. في النهاية ، سيتم هدم كل قطع الدومينو. لكنه لن يحدث إلا إذا توفرت هذه الشروط:

  • يجب أن يسقط الدومينو الأول لبدء الحركة. إذا لم يسقط ، فلن يحدث أي تفاعل متسلسل. هذه هي الخطوة الأساسية.
  • يجب ضبط المسافة بين قطع الدومينو المجاورة بشكل صحيح. خلاف ذلك ، قد تسقط قطعة دومينو معينة دون أن تطرق التي تليها. ثم سيتوقف التفاعل المتسلسل ولن يكتمل أبدًا. يضمن الحفاظ على المسافة الصحيحة بين الدومينو أن (P (k) Rightarrow P (k + 1) ) لكل عدد صحيح (k geq1 ).

لإثبات التضمين [P (k) Rightarrow P (k + 1) ] في الخطوة الاستقرائية ، نحتاج إلى تنفيذ خطوتين: بافتراض أن (P (k) ) صحيح ، ثم استخدامه في إثبات (P (k + 1) ) صحيح أيضًا. حتى نتمكن من تحسين الدليل الاستقرائي إلى إجراء من 3 خطوات:

  • تحقق من صحة (P (1) ).
  • افترض أن (P (k) ) صحيح لبعض الأعداد الصحيحة (k geq1 ).
  • أظهر أن (P (k + 1) ) صحيح أيضًا.

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

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

  • تأكد من قول "افترض أن الهوية صحيحة بعض عدد صحيح (k geq1 ). " لا تقل "افترض أن هذا صحيح الكل أعداد صحيحة (k geq1 ). " إذا كنا نعلم بالفعل أن النتيجة صحيحة للجميع (k geq1 ) ، فلا داعي لإثبات أي شيء على الإطلاق.
  • تأكد من تحديد المتطلب (k geq1 ). وهذا يضمن أن يبدأ التفاعل المتسلسل لقطع الدومينو الساقطة مع أول رد فعل.
  • لا تقل "let (n = k )" أو "let (n = k + 1 )." النقطة هي أنك لا تقوم بتعيين قيمة (k ) و (k + 1 ) إلى (n ). بل أنت كذلك افتراض أن البيان صحيح متي (n ) يساوي (ك ) ، واستخدامه لإثبات أن العبارة صحيحة أيضًا متي (n ) يساوي (ك + 1 ).

مثال ( PageIndex {1} label {eg: induct1-01} )

استخدم الاستقراء الرياضي لتوضيح أن [1 + 2 + 3 + cdots + n = frac {n (n + 1)} {2} ] لجميع الأعداد الصحيحة (n geq1 ).

مناقشة

في الخطوة الأساسية ، سيكون من الأسهل التحقق من جانبي المعادلة بشكل منفصل. الخطوة الاستقرائية هي الخطوة الأساسية في أي برهان استقرائي ، والجزء الأخير ، الجزء الذي يثبت صحة (P (k + 1) ) هو الجزء الأصعب من البرهان بأكمله. في هذا الصدد ، من المفيد أن نكتب بالضبط ما تعلنه الفرضية الاستقرائية ، وما نريد حقًا إثباته. في هذه المشكلة ، تدعي الفرضية الاستقرائية ذلك

[1 + 2 + 3 + cdots + k = frac {k (k + 1)} {2}. ]

نريد إثبات أن (P (k + 1) ) صحيح أيضًا. ماذا يعني (P (k + 1) ) حقًا؟ انها تقول

[1 + 2 + 3 + cdots + (k + 1) = frac {(k + 1) (k + 2)} {2}. ]

قارن بين الطرفين الأيسر لهاتين المعادلتين. الأول هو مجموع (ك ) الكميات ، والثاني هو مجموع (ك + 1 ) الكميات ، والكمية الزائدة هي الرقم الأخير (ك + 1 ). مجموع شروط (ك ) الأولى هو بالضبط ما لدينا على الجانب الأيسر من الفرضية الاستقرائية. ومن ثم ، عن طريق الكتابة

[1 + 2 + 3 + cdots + (k + 1) = 1 + 2 + cdots + k + (k + 1)، ]

يمكننا إعادة تجميع الجانب الأيمن على النحو التالي

[1 + 2 + 3 + cdots + (ك + 1) = [1 + 2 + cdots + k] + (ك + 1) ، ]

بحيث يمكن استبدال (1 + 2 + cdots + k ) بـ ( frac {k (k + 1)} {2} ) ، وفقًا للفرضية الاستقرائية. مع المعالجة الجبرية الإضافية ، نحاول إظهار أن المجموع يساوي ( frac {(k + 1) (k + 2)} {2} ).

نحن ننطلق من الحث على ن). عندما (n = 1 ) ، يتقلص الجانب الأيسر من الهوية إلى 1 ، ويصبح الجانب الأيمن ( frac {1 cdot2} {2} = 1 ) ؛ ومن ثم ، فإن الهوية تصمد عندما (n = 1 ). افترض أنه يحمل عندما (n = k ) لبعض الأعداد الصحيحة (k geq1 ) ؛ هذا هو ، افترض ذلك

[1 + 2 + 3 + cdots + k = frac {k (k + 1)} {2} ]

لبعض الأعداد الصحيحة (k geq1 ). نريد أن نظهر أنه ينطبق أيضًا عند (n = k + 1 ). بعبارة أخرى ، نريد أن نظهر ذلك

[1 + 2 + 3 + cdots + (k + 1) = frac {(k + 1) (k + 2)} {2}. ]

باستخدام الفرضية الاستقرائية ، نجد

[ start {align} 1 + 2 + 3 + cdots + (k + 1) & = & 1 + 2 + 3 + cdots + k + (k + 1) & = & frac {k (k + 1)} {2} + (k + 1) & = & (k + 1) left ( frac {k} {2} +1 right) & = & (k + 1) cdot frac {k + 2} {2}. نهاية {محاذاة} ]

لذلك ، يتم الاحتفاظ بالهوية أيضًا عند (n = k + 1 ). هذا يكمل الاستقراء.

يمكننا استخدام تدوين الجمع (وتسمى أيضًا ملفات تدوين سيجما) لاختصار مبلغ. على سبيل المثال ، يمكن كتابة المجموع في المثال الأخير بصيغة

[ sum_ {i = 1} ^ n i. ]

الحرف (i ) هو مؤشر الجمع. بوضع (i = 1 ) تحت ( sum ) و (n ) أعلاه ، نعلن أن المجموع يبدأ بـ (i = 1 ) ، ويتراوح من خلال (i = 2 ) ، (i = 3 ) وهكذا حتى (i = n ). تصف الكمية التي تلي ( sum ) نمط المصطلحات التي نضيفها في التجميع. وفقا لذلك،

[ sum_ {i = 1} ^ {10} i ^ 2 = 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + cdots + 10 ^ 2. ]

بشكل عام ، يُرمز إلى مجموع (n ) المصطلحات الأولى في تسلسل ( {a_1، a_2، a_3، ldots ، } ) ( sum_ {i = 1} ^ n a_i ). لاحظ ان

[ sum_ {i = 1} ^ {k + 1} a_i = left ( sum_ {i = 1} ^ k a_i right) + a_ {k + 1}، ]

الذي يوفر الرابط بين (P (k + 1) ) و (P (k) ) في إثبات الاستقراء.

مثال ( PageIndex {2} label {eg: induct1-02} )

استخدم الاستقراء الرياضي لإظهار أنه بالنسبة لجميع الأعداد الصحيحة (n geq1 ) ، [ sum_ {i = 1} ^ ni ^ 2 = 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + cdots + n ^ 2 = frac {n (n + 1) (2n + 1)} {6}. ]

إجابه

نحن ننطلق من الحث على ن). عند (n = 1 ) ، يتقلص الجانب الأيسر إلى (1 ^ 2 = 1 ) ويصبح الجانب الأيمن ( frac {1 cdot2 cdot3} {6} = 1 ) ؛ ومن ثم ، فإن الهوية تصمد عندما (n = 1 ). افترض أنه يحمل عندما (n = k ) لبعض الأعداد الصحيحة (k geq1 ) ؛ وهذا يعني أن [ sum_ {i = 1} ^ k i ^ 2 = frac {k (k + 1) (2k + 1)} {6} ] لبعض الأعداد الصحيحة (k geq1 ). نريد أن نظهر أنه لا يزال قائما عندما (n = k + 1 ). بمعنى آخر ، نريد أن نوضح أن [ sum_ {i = 1} ^ {k + 1} i ^ 2 = frac {(k + 1) (k + 2) [2 (k + 1) +1 ]} {6} = frac {(k + 1) (k + 2) (2k + 3)} {6}. ] من الفرضية الاستقرائية ، نجد [ begin {align} sum_ {i = 1} ^ {k + 1} i ^ 2 & = & left ( sum_ {i = 1} ^ ki ^ 2 right) + (k + 1) ^ 2 & = & frac {k (k +1) (2k + 1)} {6} + (k + 1) ^ 2 [3pt] & = & textstyle frac {1} {6} ، (k + 1) [k (2k + 1) +6 (k + 1)] [3pt] & = & textstyle frac {1} {6} ، (k + 1) (2k ^ 2 + 7k + 6) [3pt] & = & textstyle frac {1} {6} ، (k + 1) (k + 2) (2k + 3). end {align} ] لذلك ، يتم الاحتفاظ بالهوية أيضًا عندما (n = k + 1 ). هذا يكمل الاستقراء.

مثال ( PageIndex {3} label {eg: induct1-03} )

استخدم الاستقراء الرياضي لتوضيح أن [3+ sum_ {i = 1} ^ n (3 + 5i) = frac {(n + 1) (5n + 6)} {2} ] لجميع الأعداد الصحيحة (n geq1 ).

إجابه

تابع بالحث على (n ). عند (n = 1 ) ، يتقلص الجانب الأيسر إلى (3+ (3 + 5) = 11 ) ويصبح الجانب الأيمن ( frac {2 cdot11} {2} = 11 ) ؛ ومن ثم ، فإن الهوية تصمد عندما (n = 1 ). افترض أنه يحمل عندما (n = k ) لبعض الأعداد الصحيحة (k geq1 ) ؛ وهذا يعني أن [3+ sum_ {i = 1} ^ k (3 + 5i) = frac {(k + 1) (5k + 6)} {2} ] لبعض الأعداد الصحيحة (k geq1 ). بعبارة أخرى ، نريد أن نوضح أن [3+ sum_ {i = 1} ^ {k + 1} (3 + 5i) = frac {[(k + 1) +1] ، [5 (k +1) +6]} {2} = frac {(k + 2) (5k + 11)} {2}. ] من الفرضية الاستقرائية ، نجد [ begin {align} 3+ sum_ { i = 1} ^ {k + 1} (3 + 5i) & = & left (3+ sum_ {i = 1} ^ k (3 + 5i) right) + [3 + 5 (k + 1) ] & = & frac {(k + 1) (5k + 6)} {2} + 5k + 8 [3pt] & = & textstyle frac {1} {2} ، [(k +1) (5k + 6) +2 (5k + 8)] [3pt] & = & textstyle frac {1} {2} ، (5k ^ 2 + 21k + 22) [3pt] & = & textstyle frac {1} {2} ، (k + 2) (5k + 11). end {align} ] هذا يكمل الاستقراء.

تمرين عملي ( PageIndex {1} label {he: induct1-01} )

حان الوقت لكتابة دليل الاستقراء الخاص بك. أثبت أن [1 cdot2 + 2 cdot3 + 3 cdot4 + cdots + n (n + 1) = frac {n (n + 1) (n + 2)} {3} ] لجميع الأعداد الصحيحة (n geq1 ).

ملاحظة

نقدم لك المساعدة في هذا الأمر ، وبعد ذلك ستكون بمفردك. نضع القالب ، كل ما عليك فعله هو ملء الفراغات.

إجابه

لبعض الأعداد الصحيحة (k geq1 ). نريد أن نظهر أنه ينطبق أيضًا عندما (n = k + 1 ) ؛ هذا هو ، نريد أن نظهر ذلك

يترتب على الفرضية الاستقرائية أن [ تبدأ {محاذاة} hskip2in & = & hskip2in + hskip1in [6pt] hskip2in & = & hskip1in + hskip1in [6pt] hskip2in & = & hskip1in. end {align} ] هذا يكمل الاستقراء.

تمرين ( PageIndex {2} label {he: induct1-02} )

استخدم الاستقراء لإثبات ذلك ، لجميع الأعداد الصحيحة الموجبة (n ) ، [1 cdot2 cdot3 + 2 cdot3 cdot4 + cdots + n (n + 1) (n + 2) = frac {n ( n + 1) (n + 2) (n + 3)} {4}. ]

تمرين ( PageIndex {3} label {he: sumfourn} )

استخدم الاستقراء لإثبات أنه بالنسبة لجميع الأعداد الصحيحة الموجبة (n ) ، [1 + 4 + 4 ^ 2 + cdots + 4 ^ n = frac {1} {3} ، (4 ^ {n + 1 } -1). ]

يجب إكمال جميع الخطوات الثلاث في الإثبات التعريفي ؛ وإلا فقد لا يكون الدليل صحيحًا.

مثال ( PageIndex {4} label {eg: induct1-04} )

لا تحاول أبدًا إثبات (P (k) Rightarrow P (k + 1) ) من خلال الأمثلة وحدها. ضع في اعتبارك [P (n): qquad n ^ 2 + n + 11 mbox {هو Prime}. ] في الخطوة الاستقرائية ، نريد إثبات ذلك [P (k) Rightarrow P (k + 1) qquad mbox {for emph {any}} k geq1. ] يؤكد الجدول التالي أنه صحيح لـ (1 leq k leq 8 ): [ start {array} {| * { 10} {c |}} hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 hline n ^ 2 + n + 11 & 13 & 17 & 23 & 31 & 41 & 53 & 67 & 83 & 101 hline end {array} ] ومع ذلك ، عندما يكون (n = 10 ) ، (n ^ 2 + n + 11 = 121 ) مركبًا. لذلك (P (9) n السهم الأيمن P (10) ). الخطوة الاستقرائية تنهار عندما (ك = 9 ).

مثال ( PageIndex {5} label {eg: induct1-05} )

الخطوة الأساسية لا تقل أهمية. ضع في اعتبارك إثبات [P (n): qquad 3n + 2 = 3q mbox {لبعض الأعداد الصحيحة $ q $} ] للجميع (n in mathbb {N} ). افترض أن (P (k) ) صحيح بالنسبة لبعض الأعداد الصحيحة (k geq1 ) ؛ أي افترض (3k + 2 = 3q ) لبعض الأعداد الصحيحة (q ). ثم [3 (ك + 1) +2 = 3 ك + 3 + 2 = 3 + 3 س = 3 (1 + ف). ] لذلك ، يمكن كتابة (3 (ك + 1) +2 ) في نفس الشكل. هذا يثبت أن (P (k + 1) ) صحيح أيضًا. هل يتبع ذلك أن (P (n) ) صحيح لجميع الأعداد الصحيحة (n geq1 )؟ نعلم أنه لا يمكن كتابة (3n + 2 ) كمضاعفات للعدد 3. ما هي المشكلة؟

المحلول

المشكلة هي: نحتاج إلى أن يكون (P (k) ) صحيحًا لقيمة واحدة على الأقل من (k ) لبدء تسلسل الآثار [P (1) Rightarrow P (2)، qquad P (2) Rightarrow P (3)، qquad P (3) Rightarrow P (4)، qquad ldots ] فشل الاستقراء لأننا لم نقم بتأسيس الخطوة الأساسية. في الواقع ، (P (1) ) خطأ. نظرًا لأن الدومينو الأول لا يسقط ، فلا يمكننا حتى بدء التفاعل المتسلسل.

ملاحظة

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

  • يمكن استخدام الاستقراء الرياضي لإثبات أن العبارة حول (n ) صحيحة لجميع الأعداد الصحيحة (n geq1 ).
  • علينا إكمال ثلاث خطوات.
  • في الخطوة الأساسية ، تحقق من عبارة (n = 1 ).
  • في الفرضية الاستقرائية ، افترض أن العبارة تصمد عند (n = k ) لبعض الأعداد الصحيحة (k geq1 ).
  • في الخطوة الاستقرائية ، استخدم المعلومات التي تم جمعها من الفرضية الاستقرائية لإثبات أن العبارة صحيحة أيضًا عندما (n = k + 1 ).
  • تأكد من إكمال جميع الخطوات الثلاث.
  • انتبه إلى الصياغة. في البداية ، اتبع النموذج عن كثب. عندما تشعر بالراحة مع العملية برمتها ، يمكنك البدء في الخروج بنفسك.

تمرين ( PageIndex {1} label {ex: induct1-01} )

استخدم الاستقراء لإثبات أن [1 ^ 3 + 2 ^ 3 + 3 ^ 3 + cdots + n ^ 3 = frac {n ^ 2 (n + 1) ^ 2} {4} ] لجميع الأعداد الصحيحة ( n geq1 ).

تمرين ( PageIndex {2} label {ex: induct1-02} )

استخدم الاستقراء لإثبات أن الهوية التالية تنطبق على جميع الأعداد الصحيحة (n geq1 ): [1 + 3 + 5 + cdots + (2n-1) = n ^ 2. ]

تمرين ( PageIndex {3} label {ex: induct1-03} )

استخدم الاستقراء لتوضيح أن [1+ frac {1} {3} + frac {1} {3 ^ 2} + cdots + frac {1} {3 ^ n} = frac {3} {2} left (1- frac {1} {3 ^ {n + 1}} right) ] لجميع الأعداد الصحيحة الموجبة (n ).

تمرين ( PageIndex {4} label {ex: induct1-04} )

استخدم الاستقراء لتأسيس الهوية التالية لأي عدد صحيح (n geq1 ): [1-3 + 9- cdots + (- 3) ^ n = frac {1 - (- 3) ^ {n + 1} } {4}. ]

تمرين ( PageIndex {5} label {ex: induct1-05} )

استخدم الاستقراء لإظهار ذلك ، لأي عدد صحيح (n geq1 ): [ sum_ {i = 1} ^ n i cdot i! = (ن + 1)! - 1. ]

تمرين ( PageIndex {6} label {ex: induct1-06} )

استخدم الاستقراء لإثبات الهوية التالية للأعداد الصحيحة (n geq1 ): [ sum_ {i = 1} ^ n frac {1} {(2i-1) (2i + 1)} = frac {n } {2n + 1}. ]

تمرين ( PageIndex {7} label {ex: induct1-07} )

قم بتقييم ( dd sum_ {i = 1} ^ n frac {1} {i (i + 1)} ) للحصول على قيم قليلة لـ (n ). ما رأيك يجب أن تكون النتيجة؟ استخدم الاستقراء لإثبات تخمينك.

تمرين ( PageIndex {8} label {ex: induct1-08} )

استخدم الاستقراء لإثبات أن [ sum_ {i = 1} ^ n (2i-1) ^ 3 = n ^ 2 (2n ^ 2-1) ] عندما يكون (n ) عددًا صحيحًا موجبًا.

تمرين ( PageIndex {9} label {ex: induct1-09} )

استخدم الاستقراء لإظهار ذلك ، لأي عدد صحيح (n geq1 ): [1 ^ 2-2 ^ 2 + 3 ^ 2- cdots + (- 1) ^ {n-1} n ^ 2 = (-1 ) ^ {n-1} ، frac {n (n + 1)} {2}. ]

تمرين ( PageIndex {10} label {ex: induct1-10} )

استخدم الاستقراء الرياضي لتوضيح أن [ sum_ {i = 1} ^ n frac {i + 4} {i (i + 1) (i + 2)} = frac {n (3n + 7)} {2 (n + 1) (n + 2)} ] لكل الأعداد الصحيحة (n geq1 ).


شاهد الفيديو: الفرق بين الإستنتاج و الإستقراء (شهر نوفمبر 2021).