Induction, Recursion & Counting

الفصل الرابع: الاستقراء الرياضي، التكرار، وطرق العد

الهدف: إثبات النظريات (Induction)، حل المشاكل بالتكرار (Recursion)، والتمييز بين التباديل والتوافيق.
1

Mathematical Induction (الاستقراء الرياضي)

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

1. Basis Step (الخطوة الأساسية): أثبت أن العبارة $P(n)$ صحيحة عند $n=1$ (أو أول قيمة ممكنة).
مثال: $P(1)$ صحيحة.
2. Inductive Hypothesis (فرضية الاستقراء): افترض أن $P(k)$ صحيحة لعدد ما $k$.
هذا هو "الجسر" الذي سنستخدمه.
3. Inductive Step (خطوة الاستقراء): استخدم الفرضية لإثبات أن $P(k+1)$ صحيحة.
الهدف: إثبات $P(k) \to P(k+1)$.
2

Strong Induction (الاستقراء القوي)

ما الفرق؟

في الاستقراء العادي، نفترض صحة $P(k)$ فقط لإثبات $P(k+1)$.
في الاستقراء القوي، نفترض صحة $P(1), P(2), \dots, P(k)$ جميعاً لإثبات $P(k+1)$.

متى نستخدمه؟
عندما نحتاج للرجوع لأكثر من خطوة واحدة للخلف (مثلاً في الأعداد الأولية، أو متتاليات مثل فيبوناتشي حيث $F_n$ يعتمد على $F_{n-1}$ و $F_{n-2}$).
3

Recursion & Algorithms

Recursive Definition

تعريف الدالة أو المجموعة بدلالة نفسها (بشرط وجود حالة توقف Base Case).

Factorial n!:
- Basis: 0! = 1
- Recursive: n! = n * (n-1)!

Program Correctness

كيف نثبت صحة خوارزمية (Loop)؟
نستخدم Loop Invariant.

  • صحيح قبل دخول الحلقة (Initialization).
  • يبقى صحيحاً بعد كل تكرار (Maintenance).
  • عند التوقف، يعطينا النتيجة المطلوبة (Termination).
4

Counting Principles

Sum Rule (قاعدة الجمع)

إذا كان الحدث A يحدث بـ $n$ طرق، و B بـ $m$ طرق (ولا يمكن حدوثهما معاً)، فإحداهما يحدث بـ $n+m$.

Product Rule (قاعدة الضرب)

إذا كان A يحدث بـ $n$ طرق، وبعده B بـ $m$ طرق، فكلاهما يحدث بـ $n \times m$.

Permutations vs Combinations

Permutations ($P$)

الترتيب مهم (Order matters).

مثال: ترتيب متسابقين في سباق (الأول يختلف عن الثاني).

$P(n, r) = \frac{n!}{(n-r)!}$
Combinations ($C$)

الترتيب غير مهم (Order doesn't matter).

مثال: اختيار 3 طلاب للجنة (لجنة {أ، ب} هي نفسها {ب، أ}).

$C(n, r) = \frac{n!}{r!(n-r)!}$
🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / التكرار

With vs Without Repetition

انتبه للسؤال!
• Permutations with repetition: $n^r$ (مثل كلمة مرور).
• Combinations with repetition: $C(n+r-1, r)$ (مثل توزيع كرات في صناديق) .

RULE / قانون

Permutations with Indistinguishable Objects

كم كلمة يمكن تكوينها من حروف "SUCCESS"؟
الحروف S و C متكررة ولا يمكن تمييزها.
القانون: $\frac{n!}{n_1! n_2! \dots}$
الحل: $\frac{7!}{3! (S) \times 2! (C) \times 1! (U) \times 1! (E)}$.

→ السابق (Ch 3) الفصل التالي (Ch 5) ←