Sequences, Induction: Proofs, Recurrence, Trees

TAKEAWAYS:

• Sequences are ordered lists defined by explicit or recursive formulas (e.g., Fibonacci: $F_n=F_{n-1}+F_{n-2}$).
• Mathematical induction proves statements for all $n\in \mathbb{N}$ via a base case and inductive step (weak/strong forms).
• Recurrence relations model problems like tree heights or algorithm steps (e.g., merge sort’s $T(n)=2T(n/2)+n$).
• Binary trees (e.g., expression trees) visualize recursion and counting (e.g., Catalan numbers for valid parentheses).
• Real-world ties: Loan interest (geometric sequences), Pathao’s ride allocation (recurrence), and NEPSE stock trends (induction proofs).
• Exam focus: Prove statements step-by-step with clear assumptions; solve recurrences using substitution/method of characteristics.

---

1. Sequences: Definitions and Types

A sequence is an ordered list of elements (finite or infinite) defined by a rule. Sequences are classified by their generating formula:

A. Explicit vs. Recursive Definitions

B. Common Sequence Types

1. Arithmetic Sequence:

   • Formula: $a_n=a_1+(n-1)d$
   • Example: Monthly loan repayments (fixed amount + interest).
   • Real-world: NTC’s monthly electricity bill increase by Rs. 50 (arithmetic with $d=50$).

2. Geometric Sequence:

   • Formula: $a_n=a_1\cdot r^{n-1}$
   • Example: Compound interest in banks (e.g., $P(1+r{)}^n$).
   • Real-world: Daraz’s "Buy 1 Get 1 Free" discount (halving price each step: $100,50,25,...$).

3. Fibonacci Sequence:

   • Recurrence: $F_n=F_{n-1}+F_{n-2}$
   • Application: Modeling population growth or tree branching.

---

2. Mathematical Induction: The Proof Technique

Induction proves statements for all natural numbers $n$ by:

1. Base Case: Verify for $n=1$ (or $n=0$).
2. Inductive Step: Assume true for $n=k$ (weak) or all $n\le k$ (strong), then prove for $n=k+1$.

A. Weak vs. Strong Induction

B. Worked Example: Sum of Odd Numbers

Statement: Prove $1+3+5+...+(2n-1)=n^2$ for all $n\ge 1$.

Proof:

1. Base Case ($n=1$): $$1=1^2\text{(True)}$$
2. Inductive Step:
   • Assume true for $n=k$: $1+3+...+(2k-1)=k^2$.
   • Prove for $n=k+1$: $$1+3+...+(2k-1)+(2(k+1)-1)=k^2+(2k+1)=(k+1{)}^2$$
   • Conclusion: By induction, the statement holds for all $n\ge 1$.

Visualization:

C. Common Pitfalls

• Skipping the base case: Always verify $n=1$!
• Incorrect inductive hypothesis: For strong induction, assume all previous cases.
• Algebraic errors: Double-check expansions (e.g., $(k+1{)}^2=k^2+2k+1$).

---

3. Recurrence Relations: Modeling Problems

A recurrence relation defines a sequence based on previous terms. Solving it gives a closed-form formula.

A. Types of Recurrences

1. Linear Recurrence:

   • Form: $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}+f(n)$
   • Example: Fibonacci ($F_n=F_{n-1}+F_{n-2}$).

2. Nonlinear Recurrence:

   • Form: $a_n=a_{n-1}^2+1$ (e.g., Ackermann function).

B. Solving Methods

C. Worked Example: Merge Sort Recurrence

Recurrence: $T(n)=2T(\lfloor n/2\rfloor )+n$ (divide-and-conquer). Solution:

1. Guess: $T(n)=O(n\log n)$.
2. Verify using substitution:
   • Assume $T(n)\le cn\log n$ for some $c>0$.
   • Show $T(n)\le 2c(n/2)\log (n/2)+n=cn\log n-cn+n$.
   • For large $n$, $-cn+n$ is dominated by $cn\log n$, so the guess holds.

Real-world Tie: Pathao’s ride allocation splits orders into regions (divide), processes them (conquer), and combines results (merge).

---

4. Binary Trees and Recursion

Recursion is visualized using binary trees, where:

• Nodes represent recursive calls.
• Leaves represent base cases.

A. Expression Trees

Convert arithmetic expressions to trees to evaluate recursively:

Post-order traversal: $3,2,1,-,+,5,\ast$ → Evaluates to $(3+(2-1))\times 5=10$.

B. Counting Trees: Catalan Numbers

The number of valid binary trees with $n$ nodes is the $n$th Catalan number: $$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$ Example: $C_3=5$ (all possible binary trees for 3 nodes).

Real-world Tie: NEPSE’s stock price brackets (valid parentheses) or Daraz’s nested discount categories.

---

5. In the Real World

---

6. Exam Tip: Proving with Induction

1. Structure:
   • Header: Clearly state "By mathematical induction, we prove..."
   • Base Case: Show $n=1$ (or $n=0$) holds.
   • Inductive Step:
     • Assume $P(k)$ is true.
     • Prove $P(k+1)$ using the assumption.
2. Common Exam Questions:
   • Prove ${\sum }_{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$.
   • Solve $T(n)=T(n-1)+n$ (recurrence for insertion sort).
3. Avoid:
   • Circular logic (e.g., assuming what you need to prove).
   • Skipping justification (always explain why the step follows).

---

7. Practice Problems

1. Prove using induction: $2+4+6+...+2n=n(n+1)$.
2. Solve the recurrence: $T(n)=T(n-1)+2$ with $T(0)=0$.
3. Draw the binary tree for $(3+4)\times (2-1)$ and compute post-order traversal.
4. Real-world: If Daraz offers "Buy 2 items, get 1 free," model the discount sequence.

---

8. Summary Table