Test: Recurrence Relations - Computer Science Engineering (CSE) MCQ

a_n=5n+a_n-1
= 5n + 5(n-1) + … + a_n-2
= 5n + 5(n-1) + 5(n − 2) +…+ a₁
= 5n + 5(n-1) + 5(n − 2) +…+ 4 [since, a1=4]
= 5n + 5(n-1) + 5(n − 2) +…+ 5.1 – 1
= 5(n + (n − 1)+…+2 + 1) – 1
= 5 * n(n+1)/ 2 – 1
a_n = 5 * n(n+1)/ 2 – 1
Now, n=64 so the answer is a₆₄ = 10399.

Look at the differences between terms: 1, 7, 31, 124,…. and these are growing by a factor of 4. So, 1⋅4 = 4, 7⋅4 = 28, 31⋅4 = 124, and so on. Note that we always end up with 3 less than the next term. So, b_n = 4b_n-1 + 3 is the recurrence relation and the initial condition is b₀ = 1.

Concept:
Recurrence Relation:
A recurrence relation relates the nth term of a sequence to its predecessors. These relations are related to recursive algorithms.

Definition:
A recurrence relation for a sequence a₀, a₁, a₂,.... is a formula (equation) that relates each term an to certain of its predecessors a₀, a₁, a₂,...., an-1. The initial conditions for such a recurrence relation specify the values of a₀, a₁, a₂,...., a_n-1. For example, the recursive formula for the sequence 3, 8, 13, 18, 23 is
a₁ = 3, a_n = a_n-1 + 1, 2≤n<∞

Calculation:
Given:
The recurrence relation , T(n) = T(n - 1)+ 2
If n = 1  then T(n) = T(n-1)+ 2 = T(1) = T(1-1)+ 2 = T(0) + 2 =5 + 2 = 7   // Value of T(0) given in Question
If n= 2  then T(n) = T(n-1)+ 2 = T(1) = T(2-1)+ 2 = T(1) + 2 =7 + 2 = 9   // Value of T(1) is 7 
If n= 3  then T(n) = T(n-1)+ 2 = T(1) = T(3-1)+ 2 = T(2) + 2 =9 + 2 = 11   // Value of T(2) is 9
Therefore, above pattern can be written in the form of
T(n) = 2n+ 5 
If n= 1 then T(n) = 2n+ 5 = T(1) = 2(1)+ 5 = T(1) =7 
Therefore Option 3 is the correct Answer

a_n - 2a_n-1 - 4a_n-2 = 0
a_n = 2a_n-1 + 4a_n-2 (given)
a₀ = 2, a₁ = 5
a₂ = 2(5) + 4(2) = 18, a₃ = 2(18) + 4(5) = 56
a₄ = 2(56) + 4(18) = 184
∴ sequence: 2, 5, 18, 56, 184
G(x) = 2 + 5x + 18x² + 56x³ + 184x⁴ …
2xG(x) = 4x + 10x² + 36x³ + 112x⁴ …
4x²G(x) = 8 x² + 20x³ + 72x⁴ …
G(x)(1 – 2x – 4x²) = 2 + x
G(x) = 

When n = 1, a₁ = 2a₀ + 3, Now a₂ = 2a₁ + 3. By substitution, we get a₂ = 2(2a₀ + 3) + 3.
Regrouping the terms, we get a₄ = 141, where a₀ = 6.

Rewrite the recurrence relation b_{n -} 8b_n-1 + 12b_n-2 = 0. Now from the characteristic equation: x² − 8x + 12 = 0 we have x: (x−2)(x−6) = 0, so x = 2 and x = 6 are the characteristic roots. Therefore the solution to the recurrence relation will have the form: b_n = b2ⁿ + c6ⁿ. To find b and c, set n = 0 and n = 1 to get a system of two equations with two unknowns: 3 = b2⁰ + c6⁰ = b + c, and 4 = b2¹ + c6¹ = 2b + 6c. Solving this system gives c=-1/2 and b = 7/2. So the solution to the recurrence relation is, b_n = 7/2*2ⁿ − 1/2*6ⁿ.

When n= 1, a₁ = 17a₀ + 30, Now a₂ = 17a₁ + 30*2. By substitution, we get a₂ = 17(17a₀ + 30) + 60. Then regrouping the terms, we get a₂ = 1437, where a₀ = 3.

The characteristic equation of the recurrence relation is → x²−20x + 36 = 0
So, (x-2)(x-18) = 0. Hence, there are two real roots x₁=2 and x₂=18. Therefore the solution to the recurrence relation will have the form: a_n = a2ⁿ+b18ⁿ. To find a and b, set n = 0 and n = 1 to get a system of two equations with two unknowns: 4 = a2⁰ + b18⁰ = a + b and 3=a2¹ + b6¹ = 2a + 6b. Solving this system gives b = -1/2 and a = 7/2. So the solution to the recurrence relation is,
a_n = 7/2*2ⁿ−1/2*6ⁿ.

The characteristic equation of the recurrence relation is → x² − 4x - 12 = 0
So, (x-6)(x+2) = 0. Only the characteristic root is 6. Therefore the solution to the recurrence relation will have the form: a_n = a.6ⁿ+b.n.6ⁿ. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 6 = a6⁰ + b.0.6⁰ = a and 7 = a6¹ + b.1.6¹ = 2a + 6b. Solving this system gives a=6 and b=6/7. So the solution to the recurrence relation is, a_n = 6(6ⁿ) − 6/7n6ⁿ.

When n = 1, a₁ = a₀ + 2. By substitution we get, a₂ = a₁ + 2 ⇒ a₂ = (a₀ + 2)+2 and so on. So the solution to the recurrence relation, subject to the initial condition should be a_n = 2 + 2n = 2(1+n).