Unit 4: Recursion, recurrence relations and the binomial theorem
Mathematics-I notes · PTU syllabus (BSIT103/BSBC103)
On this page
Unit summary
Recursion defines things in terms of themselves, and the binomial theorem expands powers of sums. This unit covers recursion and its applications, recurrence relations and common recurrence relations, and the binomial theorem for a positive index — the general term, middle terms, particular terms and terms from the end.
After this unit you can
- Explain recursion and its applications
- Form and solve recurrence relations
- Apply the binomial theorem for a positive index
- Find general, middle, particular terms and terms from the end
PTU syllabus topics
- Recursion and its applications
- recurrence relations and common recurrence relations
- binomial theorem of positive index
- general term
- middle terms
- particular terms
- terms from the end
Expansion
(x + a)^n = Σ nCr x^(n−r) a^r
General term
T(r+1) = nCr x^(n−r) a^r
Number of terms
n + 1
Middle term (n even)
T(n/2 + 1)
Middle terms (n odd)
T((n+1)/2) and T((n+3)/2)
Topic 1
Recursion and its applications
- Recursive definition: a base case plus a rule defining larger cases from smaller ones.
Factorial
0! = 1; n! = n × (n − 1)!
Fibonacci
F0 = 0, F1 = 1; Fn = Fn−1 + Fn−2
Sum
S(1) = 1; S(n) = S(n − 1) + n
- Applications: algorithms (binary search, merge sort, tree traversal, Tower of Hanoi), grammars, fractals, divide-and-conquer.
Topic 2
Recurrence relations
- Recurrence relation: an equation defining each term of a sequence using earlier terms, with initial conditions.
Linear homogeneous with constant coefficients
an = c1 an−1 + c2 an−2
Arithmetic
an = an−1 + d gives an = a0 + nd
Geometric
an = r an−1 gives an = a0 rⁿ
Tower of Hanoi
Hn = 2Hn−1 + 1, H1 = 1, giving Hn = 2ⁿ − 1
Divide and conquer
T(n) = 2T(n/2) + n gives O(n log n)
- Solving linear homogeneous recurrences: form the characteristic equation r² − c1 r − c2 = 0; distinct roots r1, r2 give an = A r1ⁿ + B r2ⁿ; repeated root r gives an = (A + Bn) rⁿ; use initial conditions to find A and B.
Example
an = 5an−1 − 6an−2, a0 = 1, a1 = 4: r² − 5r + 6 = 0, r = 2, 3; an = A·2ⁿ + B·3ⁿ; A + B = 1, 2A + 3B = 4 → B = 2, A = −1; an = 2·3ⁿ − 2ⁿ.
Topic 3
The binomial theorem for a positive index
Expansion
(x + a)ⁿ = Σ (r = 0 to n) nCr x^(n−r) a^r
General term
T(r+1) = nCr x^(n−r) a^r
Number of terms
n + 1
nCr
n! ÷ [r!(n − r)!]
- Properties: nC0 = nCn = 1; nCr = nC(n−r); sum of coefficients = 2ⁿ (put x = a = 1).
Topic 4
Middle terms, particular terms and terms from the end
- Middle term: if n is even, one middle term T(n/2 + 1); if n is odd, two middle terms T((n+1)/2) and T((n+3)/2).
- Particular term: find r so that the power of x in the general term equals the required power (e.g., term independent of x).
- rth term from the end in (x + a)ⁿ = (n − r + 2)th term from the beginning = rth term of (a + x)ⁿ.
Example
Term independent of x in (x + 1/x)⁶: T(r+1) = 6Cr x^(6−r) x^(−r) = 6Cr x^(6−2r); 6 − 2r = 0 → r = 3; term = 6C3 = 20.
Key terms
- Recursive definition
- Definition using a base case and a rule
- Recurrence relation
- Equation defining terms by earlier terms
- Characteristic equation
- Polynomial used to solve linear recurrences
- General term
- Formula for any term of a binomial expansion
- Middle term
- Central term(s) of an expansion
Quick revision
- Factorial, Fibonacci; applications of recursion.
- Recurrences: arithmetic, geometric, Hanoi, divide and conquer.
- Characteristic equation method.
- Binomial expansion; general term; properties of nCr.
- Middle terms; particular terms; terms from the end.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Give a recursive definition of n!.
- Q2.What is a recurrence relation?
- Q3.Solve Hn = 2Hn−1 + 1 with H1 = 1.
- Q4.Write the general term of (x + a)ⁿ.
- Q5.Find the number of terms in (2x − 3)⁹.
- Q6.Find the middle term of (x + 2)⁸.
Long-answer questions
- Q1.Explain recursion and its applications with examples.
- Q2.Solve a linear homogeneous recurrence relation (numerical).
- Q3.State and explain the binomial theorem for a positive index.
- Q4.Find the middle term and the term independent of x in a given expansion (numerical).
Stuck on this unit?
Message SBS on WhatsApp for help with Mathematics-I, or to ask about studying B.Sc IT at Synetic.