0

(a) Find a recurrence relation for the number of sequences of $ \ 1s, \ 3s, \ and \ \ 5s \ $

whose terms sum to $ \ n $

(b) Repeat part $ \ (a) $ with the added condition that no $ \ 5 \ $ can be followed by a $ \ 1 \ $

(c) Repeat part $ \ (a) \ $ with the condition of no subsequence of $ \ 135 \ $

Answer:

(a)

Let $ \ \{a_n\} $ be the sequences.

The number of sequences of $ \ 1s, \ 3s , \ 5s \ $ is

$ 2^n+2^n+2^n \\ =3 \cdot 2^n \ $

Now given that the sum of the terms $ \ =n \ $ , we have

$ a_{n-1}+a_{n-3}+a_{n-5}=3 \cdot 2^n-n \ $.

This is the recurrence relation.

Am I right ? Is there any help ? Also for the next parts .

Asaf Karagila
  • 393,674
MAS
  • 10,638

1 Answers1

1

You have three choices for each element of the sequence, so the total number of sequences of length $n$ is $3^n$. For $a$, define $a(n)$ as the number of sequences adding to $n$. A sequence that sums to $n$ can end with either $1,3,5$. What is the sum before the last element in each case? That should give you your recurrence, which should look like $a(n)=$ some formula involving $a(n-1), a(n-3), a(n-5)$. For b, you need to separate sequences ending in $5$ from the others when you make the recurrence, so there will be $a(n)$ as the number of squences adding to $n$ and not ending in $5$ and $b(n)$ as the number of sequences adding to $n$ and ending in $5$. The recurrence will have two formulas, one for $a(n)$ and one for $b(n)$

Ross Millikan
  • 374,822