Sequences, Recurrence Relations & Binomial Theorem

TAKEAWAYS

• Sequences are ordered lists defined explicitly (e.g., $a_n=3n+2$) or recursively (e.g., $a_n=a_{n-1}+5$).
• Recurrence relations model dynamic systems (e.g., Fibonacci, compound interest) and are solved via characteristic equations for linear relations.
• The binomial theorem expands $(x+y{)}^n$ using coefficients from Pascal’s triangle, with applications in probability and combinatorics.
• Homogeneous vs. non-homogeneous relations differ in their solution structure (complementary + particular solutions for non-homogeneous).
• Induction proves statements for all $n$ by showing a base case and inductive step (used in binomial proofs).
• Real-world ties: Recurrence relations model loan repayments (banks), traffic flow (NTC), and app growth (Pathao’s ride demand).

---

1. Sequences: Definitions and Types

A sequence is an ordered list of numbers defined by a rule. Sequences can be:

• Explicit: Direct formula for the $n$th term (e.g., $a_n=2n+1$).
• Recursive: Defined based on previous terms (e.g., $a_n=a_{n-1}+3$, $a_0=1$).

Key Types

Arithmetic sequence with common difference $d=3$. (Image: Sascha Lill took the figures from Wikibooks and edited the c, CC BY-SA 4.0, via Wikimedia Commons)

Worked Example: Loan Repayment (Arithmetic Sequence)

A bank offers a loan with monthly payments of Rs. 5,000 increasing by Rs. 200 each month. Find the total repayment after 12 months.

• Solution:
  • First term $a_1=5000$, common difference $d=200$, $n=12$.
  • Sum: $S_{12}=\frac{12}{2}[2\times 5000+(12-1)\times 200]=6\times (10000+2200)=73,200$.
  • Answer: Total repayment = Rs. 73,200.

---

2. Recurrence Relations: Solving Dynamic Problems

A recurrence relation defines each term based on prior terms. Types:

1. Homogeneous: All terms depend on previous terms (e.g., $a_n=3a_{n-1}-2a_{n-2}$).
2. Non-homogeneous: Has an external input (e.g., $a_n=2a_{n-1}+5$).

Solving Homogeneous Linear Recurrence Relations

Step-by-Step Method:

1. Write the characteristic equation (replace $a_n$ with $r^n$).
2. Solve for roots $r_1,r_2,\dots$.
3. General solution:
   • Distinct roots: $a_n=c_1{r}_1^n+c_2{r}_2^n$.
   • Repeated roots: $a_n=(c_1+c_{2}n)r^n$.
4. Use initial conditions to find constants $c_1,c_2$.

Example: Fibonacci Sequence Recurrence: $a_n=a_{n-1}+a_{n-2}$, $a_0=0$, $a_1=1$.

• Characteristic equation: $r^2-r-1=0$ → Roots: $r=\frac{1\pm \sqrt{5}}{2}$.
• Solution: $a_n=\frac{1}{\sqrt{5}}\left({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right)$.

Plot of $a_n$ vs. $n$ showing exponential growth. (Image: Prokofiev, CC BY-SA 3.0, via Wikimedia Commons)

Non-Homogeneous Relations: Particular Solutions

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

1. Homogeneous solution: $a_n^{(h)}=c\cdot 2^n$.
2. Particular solution: Guess $a_n^{(p)}=A\cdot 3^n$ (since $3^n$ is the non-homogeneous term).
3. Substitute into recurrence: $A\cdot 3^n=2A\cdot 3^{n-1}+3^n$ → $A=3$.
4. General solution: $a_n=c\cdot 2^n+3\cdot 3^n$.
5. Use $a_0=1$ to find $c=-2$. Final solution: $a_n=-2\cdot 2^n+3^{n+1}$.

---

3. Binomial Theorem: Expansions and Combinations

The binomial theorem states: $$(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$$ where $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$ is the binomial coefficient.

Pascal’s Triangle and Binomial Coefficients

Each entry is the sum of the two above it. Row $n$ gives coefficients for $(x+y{)}^n$:

Row 0:        1
Row 1:      1   1
Row 2:    1   2   1
Row 3:  1   3   3   1
...

Example: Expand $(x+2y{)}^4$: $$(x+2y{)}^4=(\genfrac{}{}{0ex}{}{4}{0})x^4(2y{)}^0+\left(\genfrac{}{}{0ex}{}{4}{1}\right)x^3(2y{)}^1+(\genfrac{}{}{0ex}{}{4}{2})x^2(2y{)}^2+\left(\genfrac{}{}{0ex}{}{4}{3}\right)x^1(2y{)}^3+(\genfrac{}{}{0ex}{}{4}{4})x^0(2y{)}^4$$ $$=x^4+8x^{3}y+24x^2{y}^2+32x{y}^3+16y^4$$

Proof Using Induction (Exam Tip!)

Statement: Sum of first $n$ positive integers $S=\frac{n(n+1)}{2}$. Proof:

1. Base case ($n=1$): $S=1=\frac{1\cdot 2}{2}$. ✔️
2. Inductive step: Assume true for $n=k$, i.e., $1+2+\cdots +k=\frac{k(k+1)}{2}$. For $n=k+1$: $$1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}.$$ Thus, true for $n=k+1$. By induction, the formula holds for all $n$.

---

4. Applications in the Real World

A. Recurrence Relations in Nepal

1. Loan Interest (Nepal Banks)

   • Problem: A loan of Rs. 1,00,000 is repaid in 5 years with monthly payments increasing by Rs. 500 (arithmetic sequence).
   • Solution: Use arithmetic series sum formula to calculate total repayment.
   • Why it matters: Helps borrowers predict total cost.

2. Traffic Flow (NTC)

   • Problem: Number of vehicles at a junction follows $a_n=1.1a_{n-1}+200$ (geometric + constant).
   • Solution: Solve non-homogeneous recurrence to forecast congestion.

3. App Growth (Pathao)

   • Problem: Daily rides grow as $a_n=1.2a_{n-1}+500$ (word-of-mouth + marketing).
   • Solution: Recurrence models user acquisition for scaling.

B. Binomial Theorem in Probability

• Example: Probability of exactly 3 heads in 5 coin tosses: $$\left(\genfrac{}{}{0ex}{}{5}{3}\right){\left(\frac{1}{2}\right)}^3{\left(\frac{1}{2}\right)}^2=10\times \frac{1}{32}=\frac{5}{16}.$$
• Used by: Khalti (fraud detection via binomial probability of transaction patterns).

---

5. Exam Tips

1. For sequences:

   • Memorize arithmetic/geometric sum formulas.
   • In exams, always check initial terms when given a recurrence.

2. For recurrence relations:

   • Homogeneous: Solve characteristic equation first.
   • Non-homogeneous: Guess particular solution based on the input term (e.g., $3^n$ → $A\cdot 3^n$).
   • Common mistakes: Forgetting initial conditions or misapplying roots.

3. For binomial theorem:

   • Pascal’s triangle is your friend for small $n$.
   • Induction proofs require clear base case and inductive step.
   • Exam trick: For $(x+y{)}^n$, write terms in order of descending $x$.

4. Real-world connections:

   • Loans/interest: Arithmetic/geometric sequences.
   • Network traffic: Recurrence relations (e.g., packet delays).
   • Probability: Binomial coefficients (e.g., NEPSE stock success rates).

---

Final Note: Practice deriving recurrence relations from word problems (e.g., "A population grows by 10% annually with 500 new births each year"). Master this unit, and you’ll ace problems on sequences, expansions, and dynamic systems!