recategorized by
501 views
3 votes
3 votes

Consider the sequence $\langle s_n : n \geq 0 \rangle$ defined as follows: $s_0=0, s_1=1, s_2=1$, and $s_n = s_{n-1} +s_{n-2}+s_{n-3}$, for $n \geq 3$. Which of the following statements is FALSE?

  1. $s_{4k}$ is even, for any $ k \geq 0$
  2. $s_{4k+1}$ is odd, for any $ k \geq 0$
  3. $s_{4k+2}$ is odd, for any $ k \geq 0$
  4. $s_n$ is a multople of 3, for only finitely many values of $n$
  5. $s_{4k+3}$ is even, for any $ k \geq 0$
recategorized by

2 Answers

1 votes
1 votes

First note that:

  • Even + Odd + Odd = Even.
  • Odd + Odd + Even = Even.
  • Odd + Even + Even = Odd. 

Now, the given series in Even Odd terms is:

E,O,O,E,E,O,O,E,...

Therefore all options except D is true. D is false since there are infinite multiples of 3 in the series. 

0 votes
0 votes
$S_{3} is even$ ,

$S_{4k} is even+ odd + odd$ =EVEN

$S_{4k+1} is even +even + odd$  = ODD

$S_{4k+2} is odd +even + even$ =ODD

$S_{4k+3} is odd +odd + even$ = EVEN

Above is true always so pattern $S_{4},S_{5},S_{6}....$ will be $E,O,O,E,E,O,O,E....$

 

we can also view this as question of TOC

we have to scan last 3 symbol to determine current symbol like if last 3 symbol are E,O,O then next will be E

there are only two possible state and 4 transations
Answer:

Related questions