Previous Year Questions: Recurrence | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

Q1: The Lucas sequence L_n is defined by the recurrence relation:
L_n = L_n−1 + L_n−2, for n ≥ 3,
with L₁ = 1 and L₂ = 3
Which one of the options given is TRUE?  (2023)
(a)  
(b)
(c)
(d)
Ans: (a)
Sol: By using n = 1, options can be eliminated easily and there are methods like solving linear homogeneous recurrenceby making characteristic equation, generating function etc.
As answer is added here by converting L_n − L_n−1 − L_n−2 = 0 to characteristic equation r² − r − 1 = 0 by assuming solution L_n = crⁿ; c > 0
But the question is “why” we assume so ?  
So, we can use an approach of Linear Algebra and prove that our assumption is correct because it is difficult to assumesomething while solving this question first time because we might find difficulty to assume it without having any reason.
So,this method is long but answer your question of "Why ?"
Here, we have given a difference equation of order two as L_n = L_n−1 + L_n−2  ;n ≥ 3

The idea is, we will make the system of two simultaneous difference equations of order one from this linear difference equationof order 2 and then write it in the matrix form and solve this system.

Assume, L_n−2 = M_n−1 or M_n = L_n−1

And this way, we have a system of two difference equations of order one as :

L_n = L_n−1+M_n−1    (1)

M_n = L_n−1+0M_n−1    (2)

Now, if we write this system in the matrix form as:
Now, we replace
So,
In this way, we get,
Hence,
Now, say,
Now, to find Aⁿ⁻², we need to find Aⁿ and for that we can use the idea of Cayley-Hamilton theorem.
(Aⁿ can be computed with the use of Diagonalization concept by finding eigenvalues and eigenvectors for the matrix A.)
Suppose, λ is an eigenvalue for the matrix A. So characteristic equation will be:
det(A - λI) = 0
So, characteristic equation will be:
λ² - λ - 1 = 0
This is the same characteristic equation which we got while solving linear homogeneous recurrence and so, you can say, this is a proof for making that characteristic equation for linear homogeneous recurrence withconstant coefficient  without assuming solution of the recurrencein the form of cλⁿ or λⁿ.
Now, According to the Cayley-Hamilton theorem, every square matrix A satisfies its characteristic equation and so,
A² - A - I = 0
A²  = A  + I
A³ = A²  + A = 2A + I
A⁴ = 2A² + A = 3A + 2I

Hence, you can write Aⁿ = aA + bI for some arbitrary constant a and b.
Hence, 

So,  and
Since, λ² −λ − 1 = 0 gives
So, we get,
Now, put a and b in Aⁿ = aA + bI, we get:  
 
And so,
  
Now, finally, by (3), we get:
  
After solving it, we get,

Q2: Consider the following recurrence:
f(1) = 1;
f(2n) = 2f(n) − 1, for n ≥ 1;
f(2n + 1) = 2f(n) + 1, for n ≥ 1.
Then, which of the following statements is/are TRUE?
MSQ  (2022)
(a) f(2ⁿ−1) = 2ⁿ−1
(b) $f\left(2n\right)=1$f(2ⁿ) = 1
(c) = 2ⁿ⁺¹+1
(d) $f(2n+1)=2n+1$f(2ⁿ + 1) = 2ⁿ + 1
Ans: (a, b, c)
Sol: Edit: To do this question quickly in exam, you can do something like informal induction:
A) Let, f(2ⁿ−1) = 2ⁿ−1 is true for all natural n≥1, it means f(2ⁿ⁻¹−1) = 2ⁿ⁻¹−1 is also true for n ≥ 2.
Now,
f(2ⁿ − 1) = f((2ⁿ − 1 − 1) + 1) = f(2ⁿ − 2 + 1) = f(2(2ⁿ⁻¹−1) + 1)
= 2f(2ⁿ⁻¹−1) + 1 = 2(2ⁿ⁻¹−1) + 1 = 2ⁿ−1
Similarly,
B) f(2ⁿ) = f(2 × 2ⁿ⁻¹) = 2f(2ⁿ⁻¹) − 1 = 2 × 1 − 1 = 1
C) f(5.2ⁿ) = f(2(5 × 2ⁿ⁻¹)) = 2f(5 × 2ⁿ⁻¹) − 1
= 2 × (2ⁿ + 1) − 1 =2ⁿ⁺¹ + 1
D) f(2ⁿ+1) = f(2 × 2ⁿ⁻¹ + 1) = 2f(2ⁿ⁻¹) + 1 = 2 × 1 + 1 = 3
Hence, A, B and C are correct options

_____________________

Given: f(2n) = 2f(n) − 1 and f(2n + 1) = 2f(n) + 1 for n ≥ 1
Now, I shall check options one by one.
Option (B):
f(2ⁿ) = 2f(2ⁿ/2) − 1 [∵ 2ⁿ is an even term for n ≥ 1 and since for even terms recurrence is defined as f(2n) = 2f(n)−1  which can be written as f(n) = 2f(n/2) − 1 So, I can write f(2ⁿ) as 2f(2ⁿ/2) − 1]
So, f(2ⁿ) = 2f(2ⁿ⁻¹) − 1
= 2[2f(2ⁿ⁻²) − 1] − 1 = 2²f(2ⁿ⁻²) − 2 − 1
Like this I can write:
f(2ⁿ) = 2^kf(2^n−k)−2^k−1 − 2^k−2 −...− 1
Put n − k = 0 ⇒ k = n
So, f(2ⁿ) = 2ⁿ ∗ 1 − (1 + 2 +...+ 2ⁿ⁻¹) = 2ⁿ–((1∗(2n−1))/(2−1)) = 2ⁿ – 2ⁿ + 1 = 1
Hence, f(2ⁿ) = 1
Option (A):
Since, 2ⁿ − 1 is an odd term for n ≥ 1 So, I can get the value of f(2ⁿ − 1) from the recurrence which is defined for odd terms i.e. f(2n + 1) = 2f(n) + 1 which can be written as
So,

So,  f(2ⁿ − 1) = 2f(2ⁿ⁻¹ − 1) + 1
= 2[2f(2ⁿ⁻² – 1) + 1] + 1 = 2²f(2ⁿ⁻² − 1) + 2 + 1
Like this I can write as:
f(2ⁿ – 1) = 2^kf(2^n−k − 1) + 2^k−1 + 2^k−2 +...+ 1
Put 2^n−k − 1 = 1 ⇒ 2^n−k = 2 ⇒ n−k = 1 ⇒ k = n − 1
So,
f(2ⁿ–1) = 2ⁿ⁻¹ ∗ 1 + 2ⁿ⁻² + 2ⁿ⁻³ +...+ 1 = 1 + 2 +….+ 2ⁿ⁻¹
=((2ⁿ − 1)/(2 − 1)) = 2ⁿ – 1
So, f(2ⁿ – 1) = 2ⁿ – 1
Option (C):
For n ≥ 1, 5 × 2ⁿ will give an even value, So, I can use recurrence which is defined for even terms i.e. f(2n) = 2f(n) − 1  which can be written as f(n) = 2f(n/2) − 1 So, I can write f(5 × 2ⁿ) as  
So,
f(5×2ⁿ) = 2f(5 × 2ⁿ⁻¹) – 1
= 2[2f(5 × 2ⁿ⁻²) – 1] −1 = 2²f(5 × 2ⁿ⁻²)–2 − 1
Like this I can write:
f(5 × 2ⁿ) = 2^kf(5 × 2^n−k) – 2^k−1 – 2^k−2 −...− 2⁰
Since f(5 × 2¹) = f(10) = 2f(5) − 1 = 2[2f(2) + 1] − 1 = 2[2 + 1] − 1 = 5
So, put 5 × 2^n−k = 10 ⇒ 2^n−k = 2¹ ⇒ n − k = 1 ⇒ k = n − 1
So,
f(5 x 2ⁿ) = 2^n-1 x 5-2^n-2 - 2^n-3 - ... -1 = 5 x 2^n-1 - [1 + 2 + ... + 2^n-2]
f(5 x 2ⁿ) = 5 x 5-2^n-2 - = 5 x 2^n-1 - 2^n-1 + 1 = 2^n-1 (5 - 1) + 1
f(5 x 2ⁿ) = 2^n-2 x 2² + 1 = 2ⁿ⁺¹ + 1
Option (D):
Since, 2ⁿ + 1 is an odd value for n ≥ 1, So, I can get the values for f(2ⁿ + 1) from the recurrence which is defined for odd values of f. i.e. f(2n + 1) = 2f(n) + 1 which can be written as f(n)
So,
f(2ⁿ + 1) =  2f(2^{n - 1}) + 1 = 2 x 1 + 1 = 3
Hence, Answer: A, B, C (By putting values of n and evaluating f(.), we can eliminate some option also here.)

Q3: Consider the recurrence relation a₁ = 8, a_n = 6n² + 2n + a_n−1. Let a₉₉ = K × 10⁴. The value of K is .  (2016 SET-1)
(a) 198
(b) 148
(c) 226
(d) 312
Ans: (a)
Sol: a_n = 6n² + 2n + a_n-1
= 6n² + 2n + 6(n − 1)² + 2(n − 1) + a_n−2
= 6n² + 2n + 6(n − 1)² + 2(n − 1) + 6(n − 2)² + 2(n − 2) +......+ a₁
= 6n² + 2n + 6(n−1)² + 2(n−1) + 6(n − 2)² + 2(n − 2)+......+ 6.12 + 2.1
= 6(n² + (n − 1)² +...+ 2² + 1²) + 2(n + (n − 1) + ...+ 2 + 1)
= n(n + 1)(2n + 1 + 1)
a_n = 2n(n + 1)²
for n = 99 a₉₉ = 2 x 99 x (99 + 1)² = 198 x 10⁴

Q4: Let a_n be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for  a_n?  (2016 SET-1)
(a) $an=an-1+2an-2$a_n = a_n−1 + 2a_n−2 
(b) $an=an-1+an-2$a_n = a_n−1 + a_n−2
(c) a_n = 2a_n−1 + a_n−2
(d) $an=2an-1+2an-2$a_n = 2a_n−1 + 2a_n−2
Ans: (b)
Sol: a_n = a_n-1 + a_n-2
Rest of the options are already out.
Alternatively, we can get a string in a_n by appending "0" to any string in a_n−1 as well as by appending "01" to any string in a_n−2 and the two cases are mutually exclusive (no common strings) as well as exhaustive (covers all cases).  
Correct Answer: B

Q5: Let a_n represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a_n?  (2015 SET-1)
(a) $an-2+an-1+2n-2$a_n−2 + a_n−1 + 2ⁿ⁻²
(b) a_n−2 + 2a_n−1 + 2ⁿ⁻²
(c) 2a_n−2 + a_n−1 + 2ⁿ⁻²
(d) $2an-2+2an-1+2n-2$2a_n−2 + 2a_n−1 + 2ⁿ⁻²
Ans: (a)
Sol: Counting the number of bit strings NOT containing two consecutive 1's. (It is easy to derive a recurrence relation for the NOT case as shown below)
0      1

00  01  10  −3 (append both 0 and 1 to any string ending in 0, and append 0 to any string ending in 1)

000  001  010  100  101 − 5 (all strings ending in 0 give two strings and those ending in 1 give 1 string)

0000  0001  0010  0100  0101  1000  1001  1010 − 8 

⋮
 (where a_n denote the number of bit strings of length n containing two consecutive 1s)
2ⁿ − a_n = (2ⁿ⁻¹ − a_n−1) + (2ⁿ⁻² − a_n−2)
a_n = 2ⁿ⁻²(4 − 2 − 1) + a_n−1 + a_n−2
a_n = a_n−1 + a_n−2 + 2ⁿ⁻²
Correct Option: A