Sequences, Recurrence Relations & Binomial Theorem: Definitions, Solving, and Applications

TAKEAWAYS:

• Sequences are ordered lists defined by explicit formulas (e.g., $a_n=3n+2$) or recurrence relations (e.g., $a_n=a_{n-1}+5$).
• Recurrence relations model real systems (e.g., Fibonacci for tree branching, loan payments for finance) and are solved via characteristic equations or generating functions.
• The binomial theorem expands $(x+y{)}^n$ into ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^{n-k}{y}^k$, critical for probability and combinatorics.
• Linear homogeneous recurrences with constant coefficients have solutions of the form $a_n=c_1{r}_1^n+c_2{r}_2^n$ (for distinct roots $r_1,r_2$).
• Non-homogeneous recurrences require a particular solution (guess-and-check) plus the homogeneous solution.
• Combinatorial proofs of binomial identities (e.g., Pascal’s identity) use lattice paths or committee-counting.

---

Sequences: Explicit vs. Recursive Definitions

A sequence is an ordered list of numbers $a_1,a_2,a_3,\dots$. Sequences can be defined:

1. Explicitly: Direct formula for the $n$th term, e.g., $a_n=2n-1$ (odd numbers: 1, 3, 5, ...).
2. Recursively: Rule using previous terms, e.g., $a_n=a_{n-1}+3$ with $a_1=2$ (2, 5, 8, 11, ...).

Worked Example: Loan Amortization (Real-World Tie)

A bank offers a loan of Rs. 100,000 at 10% annual interest, repaid in 5 equal yearly installments. Let $a_n$ be the remaining debt after $n$ payments. The recurrence relation is: $$a_n=1.10\cdot a_{n-1}-P,$$ where $P$ is the fixed annual payment. Solve for $P$ and the sequence $a_n$.

Solution:

1. Homogeneous solution: $a_n^{(h)}=C\cdot (1.10{)}^n$.
2. Particular solution: Assume $a_n^{(p)}=A$ (constant). Substituting: $$A=1.10A-P⟹A=10P.$$
3. General solution: $a_n=C\cdot (1.10{)}^n+10P$.
4. Boundary condition: $a_0=100,000=C+10P$.
5. Final payment: $a_5=0=C\cdot (1.10{)}^5+10P$. Solving gives $P\approx \text{Rs. }26,380$.

---

Recurrence Relations: Types and Solutions

Recurrence relations define sequences based on prior terms. Key types:

Solving Linear Homogeneous Recurrences

For $a_n+5a_{n-1}-6a_{n-2}=0$:

1. Characteristic equation: $r^2+5r-6=0⟹r=1,-6$.
2. General solution: $a_n=C_1\cdot 1^n+C_2\cdot (-6{)}^n=C_1+C_2(-6{)}^n$.
3. Initial conditions: If $a_0=2$, $a_1=3$, solve for $C_1,C_2$.

Visual: Characteristic Roots and Solutions

---

Non-Homogeneous Recurrences: Method of Undetermined Coefficients

For $a_n-3a_{n-1}=2^n$:

1. Homogeneous solution: $a_n^{(h)}=C\cdot 3^n$.
2. Particular solution guess: $A\cdot 2^n$ (since $2^n$ is not a solution to the homogeneous equation).
3. Substitute and solve: $$A\cdot 2^n-3A\cdot 2^{n-1}=2^n⟹A(2-3/2)=1⟹A=4.$$
4. General solution: $a_n=C\cdot 3^n+4\cdot 2^n$.

Real-World Tie: Pathao’s Ride Queue Pathao’s algorithm for matching drivers to riders can be modeled by a recurrence relation where: $$q_n=q_{n-1}+\text{new riders}-\text{matched riders}.$$ A non-homogeneous term accounts for peak-hour surges (e.g., $f(n)=50\cdot \sin (n\pi /12)$ for daily patterns).

---

Binomial Theorem: Expansions and Combinatorial Proofs

The binomial theorem states: $$(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k.$$ Key identities:

• Pascal’s identity: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$.
• Binomial coefficients: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$.

Worked Example: Probability in NEPSE

Suppose a stock’s price changes by +1 or -1 with equal probability. The probability of a net gain of 2 after 4 days is the number of paths with 3 +1’s and 1 -1, divided by $2^4$: $$\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot {\left(\frac{1}{2}\right)}^4=\frac{4}{16}=\frac{1}{4}.$$

Visual: Binomial Coefficients as Pascal’s Triangle

---

Combinatorial Proof of ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$

Interpretation: Count subsets of an $n$-element set.

• Left side: Sum over all possible subset sizes $k$.
• Right side: Each element has 2 choices (included or excluded).

Visual: Subset Counting

---

Generating Functions (Brief Introduction)

Generating functions encode sequences as coefficients of power series: $$G(x)=\sum _{n=0}^{\infty }{a}_n{x}^n.$$ Example: For the Fibonacci sequence $F_n=F_{n-1}+F_{n-2}$ with $F_0=0,F_1=1$: $$G(x)=x+xG(x)+x^{2}G(x)⟹G(x)=\frac{x}{1-x-x^2}.$$

Real-World Tie: YouTube’s Video Recommendations YouTube’s algorithm for predicting video popularity can use generating functions to model sequences of user interactions (likes, shares) and optimize recommendations.

---

Exam Tip

1. For sequences: Always check if a recurrence is homogeneous/non-homogeneous. For non-homogeneous, guess the form of the particular solution (e.g., polynomial, exponential).
2. Binomial theorem: Memorize the expansion and identities like ${\sum }_{k=0}^n{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. Use combinatorial arguments for proofs.
3. Recurrence solving: Show all steps—characteristic equation, initial conditions, and final solution. Partial credit is often given for correct setup.
4. Real-world applications: Link recurrences to finance (loans), computer science (algorithm analysis), or biology (population growth). For example:
   • WhatsApp’s message delivery: Modeled by a recurrence where $m_n=m_{n-1}+\text{new messages}-\text{delivered messages}$.
   • Daraz’s inventory: Uses binomial coefficients to calculate probabilities of stockouts during sales.

Common Pitfalls:

• Forgetting to include the homogeneous solution when solving non-homogeneous recurrences.
• Incorrectly guessing the particular solution (e.g., assuming $A$ for a linear non-homogeneous term when the homogeneous solution already has a constant).
• Misapplying initial conditions in recurrence relations.