# Recurrence

 Question 1
The Lucas sequence $L_n$ is defined by the recurrence relation:
$L_n=L_{n-1}+L_{n-2}, \; for \; n\geq 3,$
with $L_1=1 \; and \; L_2=3$
Which one of the options given is TRUE?
 A $L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{2} \right )^n$ B $L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n - \left ( \frac{1-\sqrt{5}}{3} \right )^n$ C $L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{3} \right )^n$ D $L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n- \left ( \frac{1-\sqrt{5}}{2} \right )^n$
GATE CSE 2023   Discrete Mathematics
Question 1 Explanation:
 Question 2
Consider the following recurrence:
\begin{aligned} f(1)&=1; \\ f(2n)&=2f(n)-1, & \text{for }n \geq 1; \\ f(2n+1)&=2f(n)+1, & \text{for }n \geq 1. \end{aligned}
Then, which of the following statements is/are TRUE?
MSQ
 A $f(2^n-1)=2^n-1$ B $f(2^n)=1$ C $f(5 \dot 2^n)=2^{n+1}+1$ D $f(2^n+1)=2^n+1$
GATE CSE 2022   Discrete Mathematics
Question 2 Explanation:

 Question 3
Consider the recurrence relation $a_{1}$=8, $a_{n}=6n^{2}+2n+a_{n-1}$. Let $a_{99}= K \times 10^{4}$. The value of K is .
 A 198 B 148 C 226 D 312
GATE CSE 2016 SET-1   Discrete Mathematics
Question 3 Explanation:
 Question 4
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}$?
 A $a_{n}=a_{n-1}+2a_{n-2}$ B $a_{n}=a_{n-1}+a_{n-2}$ C $a_{n}=2a_{n-1}+a_{n-2}$ D $a_{n}=2a_{n-1}+2a_{n-2}$
GATE CSE 2016 SET-1   Discrete Mathematics
Question 4 Explanation:
 Question 5
Let $a_{n}$ represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for $a_{n}$?
 A $a_{n-2}+a_{n-1}+2^{n-2}$ B $a_{n-2}+2a_{n-1}+2^{n-2}$ C $2a_{n-2}+a_{n-1}+2^{n-2}$ D $2a_{n-2}+2a_{n-1}+2^{n-2}$
GATE CSE 2015 SET-1   Discrete Mathematics
Question 5 Explanation:

There are 5 questions to complete.

### 5 thoughts on “Recurrence”

1. Question 5 all the options are wrongly typed please correct it.

2. Question 5 all the options are wrongly typed please correct it.

• Can you please share more details.

• 3. 