# Recurrence

 Question 1
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 1 Explanation:
 Question 2
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 2 Explanation:
 Question 3
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 3 Explanation:
 Question 4
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 4 Explanation:
 Question 5
Consider the sequence $\left \langle x_n \right \rangle,\; n \geq 0$ defined by the recurrence relation $x_{n + 1} = c \cdot (x_n)^2 - 2$, where c > 0.
For which of the following values of c, does there exist a non-empty open interval (a, b) such that the sequence $x_n$ converges for all $x_0$ satisfying a < $x_0$ < b?
i. 0.25
ii. 0.35
iii. 0.45
iv. 0.5
 A i only B i and ii only C i, ii and iii only D i, ii, iii and iv
GATE IT 2007   Discrete Mathematics
Question 5 Explanation:
 Question 6
Consider the sequence $\langle x_n \rangle , \: n \geq 0$ defined by the recurrence relation $x_{n+1} = c . x^2_n -2$, where c > 0.
Suppose there exists a non-empty, open interval (a, b) such that for all $x_0$ satisfying $a \lt x_0 \lt b$, the sequence converges to a limit. The sequence converges to the value?
 A $\frac{1+\sqrt{1+8c}}{2c}$ B $\frac{1-\sqrt{1+8c}}{2c}$ C 2 D $\frac{2}{2c-1}$
GATE IT 2007   Discrete Mathematics
Question 6 Explanation:
 Question 7
Let $H_1, H_2, H_3, ...$ be harmonic numbers. Then, for $n \in Z^+, \sum_{j=1}^{n} H_j$ can be expressed as
 A $nH_{n+1} - (n + 1)$ B $(n + 1)H_n - n$ C $nH_n - n$ D $(n + 1) H_{n+1} - (n + 1)$
GATE IT 2004   Discrete Mathematics
Question 7 Explanation:
There are 7 questions to complete.