GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
171 views

Consider the sequence $S_0, S_1, S_2, \dots$ defined as follows: $S_0=0, \: S_1=1 \: $ and $S_n=2S_{n-1} + S_{n-2}$ for $n \geq 2$. Which of the following statements is FALSE?

  1. for every $n \geq 1$, $S_{2n}$ is even
  2. for every $n \geq 1$, $S_{2n+1}$ is odd
  3. for every $n \geq 1$, $S_{3n}$ is multiple of 3
  4. for every $n \geq 1$, $S_{4n}$ is multiple of 6
  5. none of the above
asked in Combinatory by Veteran (87.4k points)  
recategorized by | 171 views
$S_3 = 5$ and is not a multiple of $3$. C can be answer.

2 Answers

+9 votes
Best answer
$S_n = 2S_{n-1} + S_{n-2}$

Characterstic polynomial for this recurrence is $x^2 = 2x + 1$

$x^2 - 2x - 1 = 0 \color{maroon}{\Rightarrow x_1 = (1+\sqrt{2}), x_2 = (1-\sqrt{2})}$

The solution to the recurrence relation is of the form : $S_n = C_1*x_1^n + C_2*x_2^n$

Putting $S(0) = 0$, $\color{blue}{C_1 + C_2 = 0}$

Putting $S(1) = 1$, $\color{blue}{C_1*(1+\sqrt{2}) + C_2*(1-\sqrt{2}) = 1}$

Solving these two, we get $C_1 = \frac{1}{2\sqrt{2}}$ and $C_2 = -\frac{1}{2\sqrt{2}}$

$\large S_n = \frac{1}{2\sqrt{2}} \bigg((1+\sqrt{2})^n - (1-\sqrt{2})^n\bigg)$

$\color{navy}{S_0 = 0, S_1 = 1, S_2 = 2, S_3 = 5, S_4 = 12, S_5 = 29, S_6 = 70}$

Clearly $S_3$ and $S_6$ are not a multiple of $3$

Hence (C) is correct answer.
answered by Veteran (25.3k points)  
selected by

Nice explanation.Thanks, bro :-)

+3 votes
Sn=2Sn−1+Sn−2
S0=0
S1=1
S2=2*S1+S0=2*1+0=2
S3=2*S2+S1=2*2+1=5
likwise
S4= 2*5+2=12
S5= 2*12+5=29
S6= 2*29+12=70
S7= 2*70+29=169
S8= 2*169+70=408

option A , B and D are satisfy only C is not satisfies

hence Ans is C
answered by Active (1.2k points)  
good job.


Top Users Sep 2017
  1. Habibkhan

    8312 Points

  2. Warrior

    2862 Points

  3. rishu_darkshadow

    2796 Points

  4. Arjun

    2766 Points

  5. A_i_$_h

    2526 Points

  6. manu00x

    2094 Points

  7. nikunj

    1980 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1810 Points

  10. SiddharthMahapatra

    1718 Points


26,283 questions
33,842 answers
80,383 comments
31,193 users