The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+7 votes
204 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 (99k points)
recategorized by | 204 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\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.
answered by Veteran (27.6k points)
edited ago 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.6k points)
good job.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,066 questions
36,872 answers
91,629 comments
34,760 users