edited by
1,918 views
15 votes
15 votes

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
edited by

2 Answers

Best answer
17 votes
17 votes

$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\times x_1^n + C_2\times x_2^n$

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

Putting $S(1) = 1$, $\color{blue}{C_1\times (1+\sqrt{2}) + C_2\times (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.

edited by
6 votes
6 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
Answer:

Related questions

15 votes
15 votes
2 answers
2
go_editor asked Dec 21, 2016
2,082 views
How many distinct words can be formed by permuting the letters of the word $\text{ABRACADABRA}?$$\frac{11!}{5! \: 2! \: 2!}$$\frac{11!}{5! \: 4! }$$11! \: 5! \: 2! \: 2!\...
19 votes
19 votes
4 answers
3
go_editor asked Dec 21, 2016
4,039 views
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins?$3^{35}$$3^{50}-2^{50}$$\binom{35}{2}$$\bino...