TheCATExam
Sign in

CAT 2021 Slot 1 — QA Question 21

Miscellaneous ProgressionsEasy

If x0 = 1, x1 = 2 and xn+2 = 1+xn+1xn, n = 0, 1, 2, 3, …, then x2021 is equal to

Answer & solution

  • A

    1

  • B

    3

  • C

    4

  • 2

Solution

Easy

Recurrences like this almost always become periodic. Compute the first several terms directly from xn+2=1+xn+1xnx_{n+2}=\dfrac{1+x_{n+1}}{x_n} until the starting pair (1,2)(1,2) reappears; that reveals the period. Then reduce 20212021 modulo the period.

1

Generate terms. Start from x0=1, x1=2x_0=1,\ x_1=2.

x2=1+x1x0=1+21=3x3=1+x2x1=1+32=2x4=1+x3x2=1+23=1x5=1+x4x3=1+12=1x6=1+x5x4=1+11=2\begin{aligned} &x_2=\frac{1+x_1}{x_0}=\frac{1+2}{1}=3\\ &x_3=\frac{1+x_2}{x_1}=\frac{1+3}{2}=2\\ &x_4=\frac{1+x_3}{x_2}=\frac{1+2}{3}=1\\ &x_5=\frac{1+x_4}{x_3}=\frac{1+1}{2}=1\\ &x_6=\frac{1+x_5}{x_4}=\frac{1+1}{1}=2 \end{aligned}
2

Spot the period. Since (x5,x6)=(1,2)=(x0,x1)(x_5,x_6)=(1,2)=(x_0,x_1), the sequence repeats with period 55:

1, 2, 3, 2, 1, 1, 2, 3, 2, 1,⏟repeat …⇒ xn=xn mod 5\begin{aligned} &1,\,2,\,3,\,2,\,1,\ \underbrace{1,\,2,\,3,\,2,\,1,}_{\text{repeat}}\ \dots\\ &\Rightarrow\ x_n=x_{n\bmod 5} \end{aligned}
3

Reduce the index.

2021=5×404+1⇒ 2021≡1 ( mod  5)⇒ x2021=x1=2\begin{aligned} &2021=5\times404+1\\ &\Rightarrow\ 2021\equiv 1\ (\bmod\ 5)\\ &\Rightarrow\ x_{2021}=x_1=2 \end{aligned}
x2021=2 (option d)x_{2021}=2\ \text{(option d)}
CAT 2021 Slot 1 QA Q21: If x 0 = 1, x 1 = 2 and x n+2 = 1 + x n + 1 x n , n = 0, 1, 2, 3, …, then x 2021 is equal to — Solution | TheCATExam