📚 الفصل ٨: تقنيات العد المتقدمة

CS285: الرياضيات المتقطعة - دليل دراسة

📑 المحتويات

١. مقدمة في علاقات التكرار

📖 تعريف: علاقة التكرار (R.R.)

علاقة التكرار للمتتالية {aₙ} هي معادلة تعبِّر عن aₙ بدلالة حد أو أكثر من الحدود السابقة a₀, ..., aₙ₋₁ ، وذلك لكل الأعداد الصحيحة n حيث n ≥ n₀ ، و n₀ عدد صحيح غير سالب.

بكلام ثاني: هي تعريف عودي بدون الحالات الأساسية.

📖 تعريف: الحل

نقول عن متتالية إنها حل لعلاقة تكرار إذا كانت حدودها تحقق العلاقة.

💡 مثال: تطبيق مالي

المسألة: واحد أودع ١٠,٠٠٠ ريال في حساب توفير بعائد ١١% سنوياً، الفائدة مركبة سنوياً. كم بيصير في الحساب بعد ٣٠ سنة؟

الحل:

نفرض Pₙ هو المبلغ بعد n سنة.

Pₙ = Pₙ₋₁ + 0.11Pₙ₋₁ = 1.11Pₙ₋₁

الشرط الابتدائي: P₀ = 10,000

التعويض المتكرر للأمام:

P₁ = 1.11P₀
P₂ = 1.11P₁ = (1.11)²P₀
P₃ = 1.11P₂ = (1.11)³P₀
⋮
Pₙ = (1.11)ⁿP₀ = (1.11)ⁿ × 10,000

الجواب النهائي:

P₃₀ = (1.11)³⁰ × 10,000 = 228,992.97 ريال

💡 مثال: تحديد الحلول

عندنا علاقة التكرار: aₙ = 2aₙ₋₁ - aₙ₋₂ لكل n ≥ 2

وش من هالخيارات تعتبر حلول؟

  • aₙ = 3n → ✓ أيوه
  • aₙ = 2ⁿ → ✗ لا
  • aₙ = 5 → ✓ أيوه

٢. علاقات التكرار الخطية المتجانسة

📖 تعريف: ك-لي هوم ريكوكو (k‑LiHoReCoCo)

علاقة تكرار خطية متجانسة من درجة k بمعاملات ثابتة هي علاقة على الشكل:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

حيث cᵢ كلها أعداد حقيقية، و cₖ ≠ 0.

الخصائص الرئيسية:

  • خطية: الطرف الأيمن مجموع حدود سابقة مضروبة في دالة في n
  • متجانسة: ما فيه حدود غير مضاعفات aⱼ
  • معاملات ثابتة: كل معامل ثابت (ما يعتمد على n)
  • درجة k: aₙ معبر عنها بدلالة الـ k حد السابقة

💡 أمثلة: تصنيف علاقات التكرار

علاقة التكرار خطية؟ متجانسة؟ الدرجة معاملات ثابتة؟
Pₙ = 1.11Pₙ₋₁ ✓ نعم ✓ نعم ١ ✓ نعم
fₙ = fₙ₋₁ + fₙ₋₂ ✓ نعم ✓ نعم ٢ ✓ نعم
aₙ = aₙ₋₁ + a²ₙ₋₂ ✗ لا - - -
Hₙ = 2Hₙ₋₁ + 1 ✓ نعم ✗ لا ١ ✓ نعم
Bₙ = nBₙ₋₁ ✓ نعم ✓ نعم ١ ✗ لا

⚠️ فكرة أساسية

الطريقة الأساسية لحل علاقات التكرار الخطية المتجانسة إننا ندور حلول على الشكل aₙ = rⁿ ، حيث r ثابت.

٣. حل علاقات التكرار الخطية المتجانسة من الدرجة الثانية

🎯 طريقة المعادلة المميزة

لعلاقة التكرار: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂

نفترض aₙ = rⁿ يكون حل إذا وفقط إذا:

rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻²

بالقسمة على rⁿ⁻² نحصل على المعادلة المميزة:

r² - c₁r - c₂ = 0

📐 نظرية ١: حالة الجذور المختلفة

ليكن c₁ و c₂ عددين حقيقيين. إذا كان للمعادلة r² - c₁r - c₂ = 0 جذرين مختلفين r₁ و r₂ (r₁ ≠ r₂).

فإن المتتالية {aₙ} حل لعلاقة التكرار aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ إذا وفقط إذا:

aₙ = α₁r₁ⁿ + α₂r₂ⁿ

لكل n = 0, 1, 2, ... ، حيث α₁ و α₂ ثوابت.

💡 مثال: تطبيق النظرية ١

المسألة: حل علاقة التكرار aₙ = aₙ₋₁ + 2aₙ₋₂ بشرط a₀ = 2 و a₁ = 7.

خطوات الحل:

  1. نكوِّن المعادلة المميزة:
    r² - r - 2 = 0
  2. نحل الجذور:
    r² - r - 2 = (r - 2)(r + 1) = 0
    r = 2 أو r = -1
  3. الصورة العامة للحل:
    aₙ = α₁(2)ⁿ + α₂(-1)ⁿ
  4. نستخدم الشروط الابتدائية عشان نطلع α₁ و α₂:
    a₀ = 2: α₁(2)⁰ + α₂(-1)⁰ = α₁ + α₂ = 2
    a₁ = 7: α₁(2)¹ + α₂(-1)¹ = 2α₁ - α₂ = 7
  5. نحل نظام المعادلات:
    α₂ = 2 - α₁
    7 = 2α₁ - (2 - α₁) = 3α₁ - 2
    9 = 3α₁ → α₁ = 3
    α₂ = -1
  6. الحل النهائي:
    aₙ = 3·2ⁿ - (-1)ⁿ

التدقيق: {aₙ≥₀} = 2, 7, 11, 25, 47, 97, ... صح ✓

📐 نظرية ٢: حالة الجذر المكرر

ليكن c₁ و c₂ عددين حقيقيين و c₂ ≠ 0. إذا كان للمعادلة r² - c₁r - c₂ = 0 جذر مكرر واحد r₀.

فإن المتتالية {aₙ} حل لعلاقة التكرار aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ إذا وفقط إذا:

aₙ = α₁r₀ⁿ + α₂nr₀ⁿ

لكل n = 0, 1, 2, ... ، حيث α₁ و α₂ ثوابت.

💡 مثال: تطبيق النظرية ٢

المسألة: حل علاقة التكرار aₙ = 6aₙ₋₁ - 9aₙ₋₂ بشرط a₀ = 1 و a₁ = 6.

خطوات الحل:

  1. المعادلة المميزة:
    r² - 6r + 9 = 0
  2. حل الجذور:
    r² - 6r + 9 = (r - 3)² = 0
    r = 3 (جذر مكرر)
  3. الصورة العامة (جذر مكرر):
    aₙ = α₁(3)ⁿ + α₂n(3)ⁿ
  4. نستخدم الشروط الابتدائية:
    a₀ = 1: α₁(3)⁰ + α₂(0)(3)⁰ = α₁ = 1
    a₁ = 6: α₁(3)¹ + α₂(1)(3)¹ = 3α₁ + 3α₂ = 6
  5. نحسب الثوابت:
    α₁ = 1
    3(1) + 3α₂ = 6 → 3α₂ = 3 → α₂ = 1
  6. الحل النهائي:
    aₙ = 3ⁿ + n·3ⁿ = (1 + n)3ⁿ

📋 إجراء الحل لـ ٢-لي هوم ريكوكو

لعلاقات التكرار على الشكل: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂

  1. كوِّن المعادلة المميزة: r² - c₁r - c₂ = 0
  2. حل الجذور المميزة
  3. اكتب الحل العام:
    • إذا كان في جذرين مختلفين: aₙ = α₁r₁ⁿ + α₂r₂ⁿ
    • إذا كان في جذر مكرر: aₙ = α₁r₀ⁿ + α₂nr₀ⁿ
  4. استخدم الشروط الابتدائية (مثل a₀ و a₁) عشان تطلع α₁ و α₂
  5. اكتب الحل النهائي وعوّض قيم α₁ و α₂
  6. تدقق حلك بحساب أول كم حد

٤. حل علاقات التكرار الخطية المتجانسة من درجة اعتباطية

📐 نظرية ٣: جذور مختلفة - الحالة العامة

ليكن c₁, c₂, ..., cₖ أعداداً حقيقية. نفرض أن المعادلة المميزة:

rᵏ - c₁rᵏ⁻¹ - ... - cₖ = 0

لها k جذراً مختلفاً r₁, r₂, ..., rₖ.

فإن المتتالية {aₙ} حل لعلاقة التكرار:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

إذا وفقط إذا:

aₙ = α₁r₁ⁿ + α₂r₂ⁿ + ... + αₖrₖⁿ

لكل n = 0, 1, 2, ... ، حيث α₁, α₂, ..., αₖ ثوابت.

💡 مثال: درجة ٣ بجذور مختلفة

المسألة: جد حل aₙ = 6aₙ₋₁ - 11aₙ₋₂ + 6aₙ₋₃ بشرط a₀ = 2, a₁ = 5, a₂ = 15.

خطوات الحل:

  1. المعادلة المميزة:
    r³ - 6r² + 11r - 6 = 0
  2. التحليل:
    (r - 1)(r - 2)(r - 3) = 0

    الجذور: r₁ = 1, r₂ = 2, r₃ = 3

  3. الحل العام:
    aₙ = α₁(1)ⁿ + α₂(2)ⁿ + α₃(3)ⁿ
  4. نستخدم الشروط الابتدائية عشان نطلع α₁, α₂, α₃ (بتحليل ثلاث معادلات بثلاث مجاهيل).

📐 نظرية ٤: الحالة العامة بجذور مكررة

ليكن c₁, c₂, ..., cₖ أعداداً حقيقية. نفرض أن المعادلة المميزة لها t جذراً مختلفاً r₁, r₂, ..., rₜ مع تكرارات m₁, m₂, ..., mₜ على التوالي.

حيث mᵢ ≥ 1 لكل i = 1, 2, ..., t و m₁ + m₂ + ... + mₜ = k.

عندها الحل العام يكون:

aₙ = (α₁,₀ + α₁,₁n + ... + α₁,ₘ₁₋₁nᵐ¹⁻¹)r₁ⁿ
    + (α₂,₀ + α₂,₁n + ... + α₂,ₘ₂₋₁nᵐ²⁻¹)r₂ⁿ
    + ... + (αₜ,₀ + αₜ,₁n + ... + αₜ,ₘₜ₋₁nᵐᵗ⁻¹)rₜⁿ

💡 مثال: جذور مكررة بتكرارات مختلفة

المسألة: إذا كانت المعادلة المميزة جذورها 2, 2, 2, 5, 5, 9 (بتكرارات 3, 2, 1) ، وش شكل الحل العام؟

الحل:

aₙ = (α₁,₀ + α₁,₁n + α₁,₂n²)(2)ⁿ + (α₂,₀ + α₂,₁n)(5)ⁿ + α₃,₀(9)ⁿ

أو بصيغة أبسط:

aₙ = (α₁ + α₂n + α₃n²)2ⁿ + (α₄ + α₅n)5ⁿ + α₆·9ⁿ

💡 مثال: حل بجذر مكرر

المسألة: جد حل aₙ = -3aₙ₋₁ - 3aₙ₋₂ - aₙ₋₃ بشرط a₀ = 1, a₁ = -2, a₂ = -1.

خطوات الحل:

  1. المعادلة المميزة:
    r³ + 3r² + 3r + 1 = 0
  2. التحليل:
    (r + 1)³ = 0

    الجذر: r = -1 بتكرار 3

  3. الحل العام:
    aₙ = (α₁ + α₂n + α₃n²)(-1)ⁿ
  4. نستخدم الشروط الابتدائية عشان نطلع α₁, α₂, α₃ (بحل نظام ثلاث معادلات).

٥. علاقات التكرار الخطية غير المتجانسة

📖 تعريف: لي نون ريكوكو (LiNoReCoCo)

علاقة تكرار خطية غير متجانسة بمعاملات ثابتة هي علاقة على الشكل:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ + F(n)

حيث c₁, c₂, ..., cₖ أعداد حقيقية، و F(n) دالة لا تساوي الصفر تماماً وتعتمد فقط على n (ليس على أي aᵢ).

علاقة التكرار بدون F(n) تسمى علاقة التكرار المتجانسة المرافقة.

🔍 كيف تفرق بين المتجانسة وغير المتجانسة؟

متجانسة: إذا حطيت كل حدود aᵢ في جهة وكل شي ثاني في الجهة الثانية، الطرف الثاني يساوي ٠.

غير متجانسة: غير كذا (الطرف الثاني مو صفر).

💡 أمثلة على علاقات غير متجانسة

  • aₙ = aₙ₋₁ + 2ⁿ (خطية، معاملات ثابتة، غير متجانسة، درجة ١)
  • aₙ = aₙ₋₁ + aₙ₋₂ + n² + n + 1 (خطية، معاملات ثابتة، غير متجانسة، درجة ٢)
  • aₙ = 3aₙ₋₁ + n3ⁿ (خطية، معاملات ثابتة، غير متجانسة، درجة ١)
  • aₙ = aₙ₋₁ + aₙ₋₂ + aₙ₋₃ + n! (خطية، معاملات ثابتة، غير متجانسة، درجة ٣)

📐 نظرية ٥: تركيب الحل العام

إذا كانت {aₙ⁽ᵖ⁾} حل خاص لعلاقة التكرار غير المتجانسة:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ + F(n)

فإن كل حل يكون على الشكل:

aₙ = aₙ⁽ᵖ⁾ + aₙ⁽ʰ⁾

حيث {aₙ⁽ʰ⁾} حل لعلاقة التكرار المتجانسة المرافقة:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

⚠️ الصيغة المفتاحية

الحل = حل خاص + حل متجانس
aₙ = aₙ⁽ᵖ⁾ + aₙ⁽ʰ⁾

🎯 إيجاد الحل الخاص

شكل الحل الخاص يعتمد على F(n):

نوع F(n) الصورة التجريبية للحل الخاص
خطي: F(n) = كثيرة حدود في n aₙ⁽ᵖ⁾ = cn + d
غير خطي: F(n) = k·sⁿ aₙ⁽ᵖ⁾ = c·sⁿ
كثيرة حدود من الدرجة d aₙ⁽ᵖ⁾ = p₀ + p₁n + ... + pₐnᵈ

💡 مثال: F(n) خطية

المسألة: جد كل حلول aₙ = 3aₙ₋₁ + 2n بشرط a₁ = 3.

خطوات الحل:

  1. حل الجزء المتجانس:
    aₙ = 3aₙ₋₁
    المعادلة المميزة: r - 3 = 0 → r = 3
    aₙ⁽ʰ⁾ = α·3ⁿ
  2. إيجاد حل خاص (F(n) = 2n خطية):

    نجرب: aₙ⁽ᵖ⁾ = cn + d

    cn + d = 3[c(n-1) + d] + 2n
    cn + d = 3cn - 3c + 3d + 2n
    cn + d = (3c + 2)n + (3d - 3c)

    نطابق المعاملات:
    n: c = 3c + 2 → -2c = 2 → c = -1
    ثابت: d = 3d - 3c → d = 3d + 3 → -2d = 3 → d = -3/2

    إذن: aₙ⁽ᵖ⁾ = -n - 3/2

  3. الحل العام:
    aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ = α·3ⁿ - n - 3/2
  4. نستخدم الشرط a₁ = 3:
    3 = α·3¹ - 1 - 3/2
    3 = 3α - 5/2
    11/2 = 3α
    α = 11/6
  5. الحل النهائي:
    aₙ = (11/6)·3ⁿ - n - 3/2

💡 مثال: F(n) غير خطية

المسألة: جد كل حلول aₙ = 5aₙ₋₁ - 6aₙ₋₂ + 7ⁿ.

خطوات الحل:

  1. حل الجزء المتجانس:
    aₙ = 5aₙ₋₁ - 6aₙ₋₂
    المعادلة المميزة: r² - 5r + 6 = 0
    (r - 2)(r - 3) = 0 → r₁ = 2, r₂ = 3
    aₙ⁽ʰ⁾ = α₁·2ⁿ + α₂·3ⁿ
  2. إيجاد حل خاص (F(n) = 7ⁿ غير خطية):

    نجرب: aₙ⁽ᵖ⁾ = c·7ⁿ

    c·7ⁿ = 5c·7ⁿ⁻¹ - 6c·7ⁿ⁻² + 7ⁿ
    c·7ⁿ = 5c·7ⁿ/7 - 6c·7ⁿ/49 + 7ⁿ
    c = 5c/7 - 6c/49 + 1
    49c = 35c - 6c + 49
    20c = 49
    c = 49/20

    إذن: aₙ⁽ᵖ⁾ = (49/20)·7ⁿ

  3. الحل العام:
    aₙ = α₁·2ⁿ + α₂·3ⁿ + (49/20)·7ⁿ

٦. أمثلة محلولة كاملة

🎓 تمرين ١: متتالية شبيهة بفيبوناتشي

المسألة: حل aₙ = aₙ₋₁ + 2aₙ₋₂ بشرط a₀ = 2, a₁ = 7.

الحل الكامل:

  1. نحدد النوع: خطية، متجانسة، درجة ٢، معاملات ثابتة
  2. المعادلة المميزة:
    r² - r - 2 = 0
  3. الحل بالقانون العام:
    r = (1 ± √(1 + 8))/2 = (1 ± 3)/2
    r₁ = 2, r₂ = -1
  4. الحل العام:
    aₙ = α₁·2ⁿ + α₂·(-1)ⁿ
  5. نطبّق الشروط الابتدائية:
    a₀ = 2: α₁ + α₂ = 2
    a₁ = 7: 2α₁ - α₂ = 7
  6. نحل النظام:
    بجمع المعادلتين: 3α₁ = 9 → α₁ = 3
    α₂ = 2 - 3 = -1
  7. الحل النهائي:
    aₙ = 3·2ⁿ - (-1)ⁿ
  8. التدقيق:
    a₀ = 3·1 - 1 = 2 ✓
    a₁ = 3·2 - (-1) = 7 ✓
    a₂ = 3·4 - 1 = 11 ✓

🎓 تمرين ٢: مع حد غير متجانس

المسألة: حل aₙ = 2aₙ₋₁ - aₙ₋₂ + 2 بشرط a₀ = 0, a₁ = 1.

الحل الكامل:

  1. نوع العلاقة: خطية، غير متجانسة، درجة ٢، معاملات ثابتة
  2. حل الجزء المتجانس (aₙ = 2aₙ₋₁ - aₙ₋₂):
    r² - 2r + 1 = 0
    (r - 1)² = 0 → r = 1 (جذر مكرر)
    aₙ⁽ʰ⁾ = (α₁ + α₂n)·1ⁿ = α₁ + α₂n
  3. إيجاد حل خاص (F(n) = 2 ثابت):

    نجرب: aₙ⁽ᵖ⁾ = c (ثابت)

    c = 2c - c + 2
    c = c + 2
    0 = 2 → تناقض!

    بما أن 1 جذر مكرر (مرتين)، نجرب: aₙ⁽ᵖ⁾ = cn²

    cn² = 2c(n-1)² - c(n-2)² + 2
    cn² = 2c(n² - 2n + 1) - c(n² - 4n + 4) + 2
    cn² = 2cn² - 4cn + 2c - cn² + 4cn - 4c + 2
    cn² = cn² - 2c + 2
    0 = -2c + 2 → c = 1
    aₙ⁽ᵖ⁾ = n²
  4. الحل العام:
    aₙ = α₁ + α₂n + n²
  5. نطبّق الشروط الابتدائية:
    a₀ = 0: α₁ + 0 + 0 = 0 → α₁ = 0
    a₁ = 1: 0 + α₂ + 1 = 1 → α₂ = 0
  6. الحل النهائي:
    aₙ = n²

٧. ملخص سريع

📝 مصطلحات أساسية

  • علاقة التكرار: معادلة تعبِّر عن aₙ بدلالة الحدود السابقة
  • خطية: الطرف الأيمن مجموع حدود سابقة (مافي قوى أو جداءات aᵢ)
  • متجانسة: ما فيه حدود غير مضاعفات aᵢ
  • معاملات ثابتة: المعاملات أعداد ثابتة، مو دوال في n
  • الدرجة k: aₙ معبر عنها باستخدام الـ k حد اللي قبلها
  • المعادلة المميزة: المعادلة اللي تطلع بعد التعويض بـ aₙ = rⁿ
  • الجذور المميزة: حلول المعادلة المميزة

🎯 خريطة طريق الحل

  1. صنِّف علاقة التكرار
    • خطية ولا غير خطية؟
    • متجانسة ولا غير متجانسة؟
    • معاملات ثابتة؟
    • كم الدرجة؟
  2. إذا كانت متجانسة:
    • اكتب المعادلة المميزة
    • جد الجذور المميزة
    • اكتب الحل العام حسب نوع الجذور
  3. إذا كانت غير متجانسة:
    • حل الجزء المتجانس المرافق
    • جد حلاً خاصاً بناءً على F(n)
    • اجمع: aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾
  4. طبّق الشروط الابتدائية عشان تطلع الثوابت
  5. اكتب الحل النهائي وتأكد منه

📋 أشكال الحل العام

نوع الجذور شكل الحل العام
جذرين مختلفين r₁, r₂ aₙ = α₁r₁ⁿ + α₂r₂ⁿ
جذر مكرر r₀ aₙ = (α₁ + α₂n)r₀ⁿ
k جذراً مختلفاً aₙ = α₁r₁ⁿ + α₂r₂ⁿ + ... + αₖrₖⁿ
جذر r بتكرار m aₙ = (α₀ + α₁n + ... + αₘ₋₁nᵐ⁻¹)rⁿ
غير متجانسة aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾

💡 أخطاء شائعة - تجنبها

  • ❌ تنسى تتأكد من وجود جذور مكررة
  • ❌ ما تضيف مضاعف n في حالة الجذر المكرر
  • ❌ تحل الجزء المتجانس بس في مسائل غير متجانسة
  • ❌ تستخدم شكل خطأ للحل الخاص
  • ❌ أخطاء حسابية في تطبيق الشروط الابتدائية
  • ❌ ما تتدقق الحل

🔑 نصائح للمذاكرة

  1. تمرن على التصنيف - أهم شيء إنك تحدد النوع بسرعة.
  2. أتقن المعادلة المميزة - هي أساس أغلب الحلول.
  3. احفظ أشكال الحلول - للجذور المختلفة والمكررة.
  4. طبّق على أمثلة - من المتجانسة وغير المتجانسة.
  5. دقق حلك - دايماً تأكد بالتعويض في الشروط الابتدائية.
  6. افهم النظرية - مو بس تحفظ القوانين.