Combinatorial Proofs & Recurrence Relations: Techniques, Trees & Real-World Models

TAKEAWAYS:

• Combinatorial proofs prove identities by counting the same object in two different ways (e.g., proving ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$ by counting subsets of a set).
• Recurrence relations define sequences recursively (e.g., Fibonacci $F_n=F_{n-1}+F_{n-2}$), solved via substitution, trees, or generating functions.
• Binary trees model recursive algorithms (e.g., merge sort’s divide-and-conquer) and are counted via Catalan numbers.
• Real-world links: eSewa’s transaction queues (recurrence), Daraz’s order routing (trees), and WhatsApp’s message delivery (combinatorial paths).
• Exam focus: Prove identities combinatorially (not algebraically), solve recurrences with clear steps, and link proofs to counting principles.

1. Combinatorial Proofs: Counting Twice

Combinatorial proofs establish identities by interpreting both sides of an equation as counts of the same object. The key steps:

1. Choose an identity (e.g., ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$).
2. Interpret the LHS as one way to count the object (e.g., subsets of a set by size).
3. Interpret the RHS as another way (e.g., subsets by inclusion/exclusion).
4. Conclude equality because both count the same thing.

Example: Proving ${\sum }_{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1}$

LHS interpretation: Count the number of ways to form a committee of any size from $n$ people, where one member is the leader (marked by $k$).

• For each $k$, choose $k$ leaders (but only 1 leader per committee), then choose $k-1$ others: $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.
• Sum over all possible committee sizes $k$.

RHS interpretation: First pick the leader ($n$ choices), then let each of the remaining $n-1$ people choose independently to join or not: $n\cdot 2^{n-1}$.

Conclusion: Both count the same thing (committees with a leader), so the identity holds.

graph LR
    A["LHS: Sum over k of k*C(n,k)"] -->|"Committee with leader"| B["Count by committee size"]
    C["RHS: n*2^(n-1)"] -->|"Pick leader, then others"| B
    B --> D["Same object: Committees with a leader"]

Real-World Link: Daraz’s Order Routing

Daraz’s delivery system routes orders through multiple hubs. Suppose an order passes through $n$ hubs, and at each hub, it can go left or right. The total number of possible paths is $2^n$. If we instead count paths by the number of left turns ($k$), we get: $$\sum _{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1}.$$ This matches our identity: Daraz’s system must handle $n{2}^{n-1}$ "left-turn" paths to ensure all routes are accounted for.

2. Recurrence Relations: Defining Sequences Recursively

A recurrence relation defines a sequence based on previous terms. Examples:

• Fibonacci: $F_n=F_{n-1}+F_{n-2}$, $F_0=0$, $F_1=1$.
• Binary trees: $T_n=2T_{n-1}+1$ (each node splits into 2 subtrees).
• Merge sort: $T(n)=2T(n/2)+n$ (divide, sort, merge).

Solving Recurrences: Methods

Example: Solving $T(n)=2T(n/2)+n$ (Merge Sort)

Recursion tree approach:

1. Draw the tree where each node splits into 2 children, and the cost at each level is $n,n/2,n/4,\dots$.
2. The total cost is the sum of all nodes: $$T(n)=n+n/2+n/4+\cdots +n/n=n{\log }_{2}n.$$
3. Visual:

Real-World Link: eSewa’s Transaction Queue eSewa processes transactions in batches. Suppose each batch splits into 2 sub-batches, and processing each batch costs $n$ units. The total cost $T(n)$ follows the same recurrence: $$T(n)=2T(n/2)+n.$$ Solving this shows eSewa’s system scales as $O(n\log n)$, explaining why transaction times grow slowly even for large $n$.

3. Binary Trees and Catalan Numbers

Binary trees are fundamental in recursion and combinatorics. The number of full binary trees with $n+1$ leaves is the $n$-th Catalan number: $$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right).$$

Example: Counting Valid Parentheses

The number of valid parentheses sequences with $n$ pairs is $C_n$. For $n=3$:

• Valid sequences: ((())), (()()), (())(), ()(()), ()()() → $C_3=5$.

Combinatorial proof:

1. LHS: Count all possible sequences of $n$ opens and $n$ closes.
2. RHS: Use Catalan’s formula or a recursive bijection to binary trees.

Real-World Link: WhatsApp’s Message Delivery WhatsApp’s message delivery can be modeled as a binary tree where each node represents a routing decision (e.g., forward to server A or B). The number of valid delivery paths for $n$ hops is $C_n$, ensuring no deadlocks.

4. Proof Techniques for Recurrences

Example: Proving $T(n)=n^2$ for $T(n)=T(n-1)+2n-1$

1. Base case: $T(1)=1=1^2$.
2. Inductive step: Assume $T(k)=k^2$. Then: $$T(k+1)=T(k)+2(k+1)-1=k^2+2k+1=(k+1{)}^2.$$
3. Conclusion: By induction, $T(n)=n^2$ for all $n$.

5. Comparing Proof Methods

6. Common Mistakes to Avoid

1. Algebraic vs. combinatorial proofs: Never manipulate symbols without a counting interpretation.
   • ❌ Wrong: "Because $(1+x{)}^n=\sum (\genfrac{}{}{0ex}{}{n}{k})x^k$, set $x=1$."
   • ✅ Right: "Both sides count subsets of an $n$-element set."
2. Ignoring base cases: Recurrence solutions must satisfy initial conditions.
3. Misapplying Catalan numbers: Only use $C_n$ for binary trees or balanced structures.

In the Real World

1. eSewa’s Transaction Processing

   • Idea: Recurrence relations model the cost of splitting transactions into sub-batches.
   • How: The recurrence $T(n)=2T(n/2)+n$ describes how processing time scales with batch size, helping eSewa optimize server loads.

2. Daraz’s Order Routing

   • Idea: Binary trees represent possible paths for orders through warehouses.
   • How: The number of valid routing paths is a Catalan number, ensuring Daraz can pre-allocate resources efficiently.

3. WhatsApp’s Message Delivery

   • Idea: Valid delivery sequences (no deadlocks) are counted by Catalan numbers.
   • How: For $n$ hops, $C_n$ ensures all possible delivery trees are accounted for, minimizing retries.

4. Nepal Rastra Bank’s Loan Amortization

   • Idea: Recurrence relations model loan repayment schedules.
   • How: The monthly payment $P$ satisfies $P=L\cdot \frac{r(1+r{)}^n}{(1+r{)}^n-1}$, derived from a recurrence on remaining principal.

Exam Tip

1. For combinatorial proofs:

   • Always state what you’re counting (e.g., "committees," "paths").
   • Show two interpretations (LHS and RHS) with clear sentences.
   • Example starter:

     "We prove ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$ by counting subsets of an $n$-element set in two ways: ..."

2. For recurrences:

   • Label your steps: "Base case," "Inductive hypothesis," "Inductive step."
   • Draw recursion trees for divide-and-conquer recurrences (e.g., merge sort).
   • Verify solutions by plugging in small values (e.g., $n=1,2,3$).

3. Common exam pitfalls:

   • Forgetting to define the recurrence’s base case.
   • Using algebraic manipulation instead of combinatorial reasoning.
   • Misapplying Catalan numbers (e.g., to unbalanced trees).

Visual Summary:

mindmap
  root((Combinatorial Proofs & Recurrences))
    Combinatorial Proofs
      Count twice
      Example: Committees
      Real: Daraz paths
    Recurrence Relations
      Define recursively
      Solve via substitution/trees
      Real: eSewa transactions
    Binary Trees
      Catalan numbers
      Real: WhatsApp delivery
    Proof Techniques
      Induction
      Substitution
      Recursion trees