Recurrence relations: initial values and solutions
Objectives and prerequisites
Build a recurrence from disjoint cases, compute early terms, solve first-order and second-order linear constant-coefficient recurrences, handle a repeated characteristic root, and verify a closed form rather than guessing from a few values. Prerequisites: counting rules, powers, elementary algebra and the meaning of an implication. Induction is explained where used.
This lesson develops exact sequence methods. It does not replace the separate analysis of divide-and-conquer algorithm runtimes, arbitrary variable-coefficient recurrences or nonlinear recurrences. All sequences below start at index 0 unless stated otherwise. Read the valid index range before substituting a base value.
1. A rule and its starting data form one problem
A recurrence expresses a term using earlier terms. The rule aₙ=2aₙ₋₁ for n≥1 does not by itself identify one sequence: a₀=1 gives 1,2,4,… while a₀=3 gives 3,6,12,… . The initial value is not optional metadata; it selects the solution.
A second-order rule usually needs two starting values because it uses the previous two terms. For aₙ=c₁aₙ₋₁+c₂aₙ₋₂, n≥2, giving a₀ and a₁ determines subsequent terms uniquely by forward calculation. Do not use the recurrence at n=1 unless it was defined there; that would introduce an unspecified a₋₁.
The order refers to how far back the recurrence reaches, not the polynomial degree of its closed form. A linear recurrence combines previous terms linearly; coefficients may or may not depend on n. Our characteristic-root method below requires constant coefficients. An added term depending on n but not on earlier a-values is a forcing term, making the recurrence nonhomogeneous.
2. Worked first-order expansion
Let a₀=4 and aₙ=2aₙ₋₁+3 for n≥1. The first values are 4,11,25,53. Expand carefully:
aₙ=2(2aₙ₋₂+3)+3=2²aₙ₋₂+3(2+1).
After k substitutions, aₙ=2ᵏaₙ₋ₖ+3(1+2+…+2ᵏ⁻¹). Set k=n to reach a₀:
aₙ=4·2ⁿ+3(2ⁿ−1)=7·2ⁿ−3.
The geometric sum has n terms, from power 0 through n−1. A common error is counting n+1 forcing contributions. An alternative shift is bₙ=aₙ+3; then bₙ=2bₙ₋₁ and b₀=7, so bₙ=7·2ⁿ.
In general, aₙ=r aₙ₋₁+d gives aₙ=rⁿa₀+d(1+r+…+rⁿ⁻¹). If r≠1, the sum equals (rⁿ−1)/(r−1). If r=1, use aₙ=a₀+nd instead of dividing by zero. An empty sum at n=0 is 0, as required to recover a₀.
3. Verification is a proof, not a visual pattern
To prove the proposed aₙ=7·2ⁿ−3, first check n=0: 7−3=4. Then suppose the formula holds at n−1. The recurrence gives
2aₙ₋₁+3=2(7·2ⁿ⁻¹−3)+3=7·2ⁿ−3.
Thus a correct previous term leads to the correct next term; starting from the base case proves every index by induction. Agreement at four small n-values suggests a candidate but does not alone prove the infinite sequence formula.
A second useful expansion is d₀=0, dₙ=dₙ₋₁+(2n−1). It gives dₙ=1+3+…+(2n−1)=n². Check the step directly: (n−1)²+2n−1=n². This is a first-order recurrence even though its solution is quadratic.
4. Distinct characteristic roots
For the homogeneous rule bₙ=c₁bₙ₋₁+c₂bₙ₋₂ with constant c₂≠0, try an exponential rⁿ. Substitution gives r²−c₁r−c₂=0, the characteristic equation. For distinct real roots r₁,r₂, the general real solution is A r₁ⁿ+B r₂ⁿ. Determine A and B from both initial values; the characteristic equation alone does not determine them.
Worked example: b₀=3, b₁=7 and bₙ=3bₙ₋₁−2bₙ₋₂ for n≥2. The polynomial r²−3r+2=(r−1)(r−2), so bₙ=A+B·2ⁿ. The equations A+B=3 and A+2B=7 give B=4, A=−1. Therefore bₙ=4·2ⁿ−1, and b₂=15, b₃=31.
Check one recurrence step: 3(4·2ⁿ⁻¹−1)−2(4·2ⁿ⁻²−1)=4·2ⁿ−1. The two initial values and this identity establish the full solution. Complex characteristic roots can also be handled with the general theory, but are outside our worked real-root cases.
5. Repeated roots require another factor
If the characteristic polynomial has one repeated root r, writing A rⁿ+B rⁿ collapses to a single independent term and cannot generally fit two arbitrary starting values. The correct second-order form is (A+Bn)rⁿ.
Let c₀=2, c₁=6 and cₙ=4cₙ₋₁−4cₙ₋₂. The characteristic polynomial is (r−2)². Hence cₙ=(A+Bn)2ⁿ. From c₀, A=2. From c₁, 2(2+B)=6, so B=1 and cₙ=(n+2)2ⁿ. Then c₂=16 and c₃=40. Reusing only C·2ⁿ would predict c₁=4 after fitting c₀=2, contradicting the stated c₁=6.
More generally, a nonzero characteristic root of multiplicity m contributes terms (A₀+A₁n+…+Aₘ₋₁nᵐ⁻¹)rⁿ. This explains the extra n-factor rather than treating it as a special mnemonic for one example.
6. Nonhomogeneous forcing and resonance
A nonhomogeneous solution can be written as one particular solution plus a general solution of the homogeneous recurrence. A trial particular form must not merely duplicate a homogeneous solution; if it does, an extra n-factor is needed. Here is a case that can be solved without guessing constants.
Let e₀=1 and eₙ=2eₙ₋₁+2ⁿ for n≥1. Divide by 2ⁿ and write uₙ=eₙ/2ⁿ. Then uₙ=uₙ₋₁+1 with u₀=1, so uₙ=n+1 and eₙ=(n+1)2ⁿ. Its first terms are 1,4,12,32.
Why would a trial K·2ⁿ fail? The difference K·2ⁿ−2K·2ⁿ⁻¹ is always 0, never the required 2ⁿ. The forcing base 2 is also a homogeneous root. A trial Kn2ⁿ succeeds because Kn2ⁿ−2K(n−1)2ⁿ⁻¹=K2ⁿ, requiring K=1. The homogeneous term C2ⁿ then supplies the initial value, C=1.
For a forcing term that is a polynomial in n times qⁿ, the standard constant-coefficient method tries a polynomial of the same degree times qⁿ, multiplied by nˢ when q is a characteristic root of multiplicity s. Verify by substitution; do not use this recipe for an unrelated nonlinear or variable-coefficient recurrence.
7. Build a counting recurrence from disjoint cases
Let fₙ count length-n binary strings with no consecutive 1s. The empty string is one valid length-0 string, so f₀=1. Both 0 and 1 are allowed at length 1, so f₁=2.
For n≥2, split by the first symbols. A valid string starting with 0 is followed by any valid length-(n−1) suffix: fₙ₋₁ possibilities. A valid string starting with 1 must next have 0, followed by any valid length-(n−2) suffix: fₙ₋₂ possibilities. The cases are disjoint and exhaustive, so fₙ=fₙ₋₁+fₙ₋₂.
The values are 1,2,3,5,8,13 for n=0 through 5. This is Fibonacci-type, but the initial values differ from F₀=0,F₁=1; in that convention fₙ=Fₙ₊₂. Do not copy a memorized Fibonacci index without checking the empty and one-symbol cases.
Solving checklist
State what aₙ counts or measures, its starting index, recurrence range and initial values. Classify the recurrence before selecting a method. Compute a few terms to detect errors, derive a candidate, and verify both initial values and the recurrence identity. Keep exact formulas distinct from asymptotic statements: aₙ=7·2ⁿ−3 is exact; aₙ=Θ(2ⁿ) describes growth and cannot replace the exact answer when a numerical term is requested.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option. Keep all stated index, domain and graph conventions.
C01. For a₀=4 and aₙ=2aₙ₋₁+3 (n≥1), which closed form is correct?
A. 4·2ⁿ+3 B. 7·2ⁿ−3 C. 4·2ⁿ+3n D. 7·2ⁿ
Answer: B
A: At n=0 this gives 7, not the required 4.
B: Expansion gives 4·2ⁿ+3(2ⁿ−1)=7·2ⁿ−3; it satisfies the initial value and recurrence.
C: The forcing contributions are themselves repeatedly doubled; they sum geometrically, not as 3n. At n=2 this gives 22 rather than 25.
D: This omits the −3 shift and gives the wrong initial value 7.
C02. Let b₀=3,b₁=7 and bₙ=3bₙ₋₁−2bₙ₋₂ for n≥2. What is b₃?
A. 15 B. 23 C. 29 D. 31
Answer: D
A: 15 is b₂=3·7−2·3, not b₃.
B: This does not follow the recurrence; b₃ uses b₂=15 and b₁=7.
C: The subtraction is 2b₁=14, so 45−14=31, not 29.
D: First b₂=21−6=15; then b₃=3·15−2·7=31. The formula 4·2³−1 agrees.
C03. For c₀=2,c₁=6 and cₙ=4cₙ₋₁−4cₙ₋₂ (n≥2), which formula is correct?
A. 2·2ⁿ B. (n+1)2ⁿ C. (n+2)2ⁿ D. 2+4n
Answer: C
A: It matches c₀ but predicts c₁=4 rather than 6; the repeated root needs a second independent term.
B: This gives c₀=1, not 2.
C: The repeated root is 2, so (A+Bn)2ⁿ applies. Initial values give A=2,B=1.
D: It matches the first two values but predicts c₂=10 instead of 4·6−4·2=16.
C04. How many length-5 binary strings contain no consecutive 1s?
A. 13 B. 8 C. 16 D. 32
Answer: A
A: With f₀=1,f₁=2 and fₙ=fₙ₋₁+fₙ₋₂, the values through n=5 are 1,2,3,5,8,13.
B: 8 is the length-4 count, an index error.
C: The valid strings are not obtained by simply halving all 32 strings; the restriction has overlapping positions.
D: 32 counts every length-5 binary string, including strings containing 11.
C05. For e₀=1 and eₙ=2eₙ₋₁+2ⁿ (n≥1), which expression equals eₙ?
A. 2ⁿ B. (n+1)2ⁿ C. n2ⁿ D. (n+1)3ⁿ
Answer: B
A: This solves the homogeneous recurrence and misses the additional forcing term.
B: Dividing by 2ⁿ gives uₙ=uₙ₋₁+1 with u₀=1, so uₙ=n+1.
C: This is a particular solution but gives e₀=0 instead of 1; the homogeneous term is missing.
D: It gives e₁=6, but the recurrence requires e₁=2·1+2=4.
C06. Let d₀=0 and dₙ=dₙ₋₁+(2n−1) for n≥1. What is dₙ?
A. 2n−1 B. 2ⁿ C. n(n+1) D. n²
Answer: D
A: This is the increment added at step n, not the accumulated sum.
B: It fails d₀=0 and does not have first difference 2n−1.
C: Its first difference is 2n, one too large.
D: The first n positive odd integers sum to n²; also (n−1)²+2n−1=n² and d₀=0.
Sources and scope
This original lesson develops a specified Discrete Mathematics topic from Section 1 of the official GATE 2027 CS syllabus. It is not a declaration that the whole subject or syllabus is complete. The syllabus confirms relevance; the institutional course chapter is a further-study reference. Worked examples, wording and practice are original.
Sources opened and checked 2026-10-14.
Sign in to keep your progress. Sign in