98 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
$S_3 = 5$ and is not a multiple of $3$. C can be 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$

selected by