# Recurrence relation involving multiple sequences

1. Apr 21, 2014

### SithsNGiggles

1. The problem statement, all variables and given/known data

I'm given a recursive sequence with the following initial terms:

$\begin{matrix} f_0(0)=1&&&f_1(0)=0\\ f_0(1)=2&&&f_1(1)=1 \end{matrix}$

Now, I'm asked to justify that we have the following recursive relations:

$\begin{cases} f_0(n)=2f_0(n-1)+f_1(n-1)\\ f_1(n)=f_0(n-1)+f_1(n-1) \end{cases}$

2. Relevant equations

I'm not sure if any context is needed, but basically, we're concerned with certain strings of length $n$ of the letters $a,b,c$. These strings must not contain $ba$ in succession, so $a,a,b$ is okay, but $a,b,a$ is not.

The number of strings ending with a particular letter is denoted by $f_1(n)$, and the number of strings that don't end with that letter is denoted $f_0(n)$.

Additionally, the total number of strings that don't contain $b,a$ (regardless of the letter with which it ends) is $f(n)=f_0(n)+f_1(n)$.

3. The attempt at a solution

I guess I'm not entirely sure what kind of answer is expected... I initially took "justify" to mean that I have to prove something by induction, but it doesn't seem to get me anywhere or I simply don't know what information to use and how.

As far as the induction thought process went, I figured I would establish the basis case (easy enough), but I can't get a handle of the induction hypothesis.

I notice that the sequence $\{f_1(0),f_0(0),f_1(1),f_0(1),...\}$ forms the Fibonacci sequence, but I suspect that has to do with the next part of the question, which involves finding a generating function. If I were to express $f_0(n)$ in terms of $f_1(n)$ and $f_0(n-1)$, would that suffice?

2. Apr 22, 2014

### haruspex

I must be missing something. Surely the number that end in b satisfying the condition will exceed the number ending in a. E.g. For n=2, three can end in b but only two can end in a. So are f0 and f1 supposed to refer to ending in a particular one of the three letters?

3. Apr 22, 2014

### SithsNGiggles

Hi haruspex. I think I left out some details regarding $f_0$ and $f_1$. The former counts the number of strings of length $n$ that do not end in $b$, and the latter counts those that DO end in $b$. So, for example, when n=2, we can have $\{aa,ac,bc,ca,cc\}$, so $f_0(2)=5$. I've ignored $ba$ due to the rule against it, and what remains are the strings ending with $b$, which are $\{ab,bb,cb\}$, making $f_1(2)=3$.

One thing I've come up with, unsure of its usefulness, is defining a new sequence,
$$g_n=\begin{cases} f_1\left(\dfrac{n}{2}\right)&\text{for even }n\\ f_0\left(\left\lfloor\dfrac{n}{2}\right\rfloor\right)&\text{for odd }n \end{cases}$$
Then I have an explicit form of the Fibonacci sequence, as $g_n=g_{n-1}+g_{n-2}$. What bothers me is that I'm not exactly sure how to connect this to the previous recurrences for $f_0$ and $f_1$.

4. Apr 22, 2014

### pasmith

Surely you should then have $f_0(0) = 0 = f_1(0)$, which doesn't tell you anything, with $f_0(1) = 2$, $f_1(1) = 1$ as the initial condition?

You are in effect asked to show that if the number of strings of length $n-1$ which don't end in 'b' is $f_0(n-1)$ and the number of strings of length $n-1$ which do end in 'b' is $f_1(n-1)$, then the number of strings of length $n$ which don't end in 'b' is $$f_0(n)=2f_0(n-1)+f_1(n-1)$$ and the number of strings of length $n$ which do end in 'b' is $$f_1(n)=f_0(n-1)+f_1(n-1).$$ To do that, you need to look at rules on which letters can follow which letters.

I don't think you are asked to actually solve these recurrences at this stage. However the recurrences are linear, so they will have solutions of the form $$\begin{pmatrix} f_0(n) \\ f_1(n) \end{pmatrix} = A\mathbf{v}_1\lambda_1^n + B\mathbf{v}_2\lambda_2^n$$ where $\lambda_1$ and $\lambda_2$ are the eigenvalues of $$\begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}$$ with corresponding eigenvectors $\mathbf{v}_1$, $\mathbf{v}_2$ and $A$ and $B$ are constants determined by the initial conditions.

5. Apr 22, 2014

### SithsNGiggles

The previous question asked me to compute the first four terms. I believe I'm treating the empty string as a string that doesn't end in $b$, so $f_0(0)=1$. I'll try to confirm with my professor.

Yeah, I get what the relations represent, I just don't understand what it means to "justify" them. Am I to think I'm expected to prove that they hold for all $n\ge1$?

As for solving, I too think I don't have to do that. My class is nearing its end and we only barely managed to introduce recurrence relations but no mention's been made of having to solve anything to say nothing of finding eigenvalues. The next part of the problem revolves around finding a closed form for $f(n)$ using some defined generating functions.

6. Apr 22, 2014

### haruspex

I think they just want you to explain how the equations are obtained.

7. Apr 22, 2014

### SithsNGiggles

Yeah it looks like I'll have to settle with that, at least until I can get a hint from my prof. Thanks to everyone that replied!

8. Apr 23, 2014

### SithsNGiggles

Hey everyone, I think I figured out the justification part, sans induction. What I did was set up a diagram, like so:
$\_~\_\cdots\_~\_$, where there are $n$ slots for one of the three letters.

Then I considered the possible outcomes you can get if you were to add an additional letter to the end. For strings that do not end in $b$, you can add $a$ or $c$ to an $n-1$ string to have two possibilities for an $n$ string that doesn't end in $b$; adding a $b$ only ups the number of words that do end in $b$.

I suspect my explanation isn't clear enough, so I'll consider an example with $n=4$. So we start with some 3-string that doesn't end in $b$, say
$\underline{a}~\underline{c}~\underline{a}$

Now we can add an $a$ or a $c$ to the end, increasing the number of $f_0$ by 2:
$\underline{a}~\underline{c}~\underline{a}~|~\underline{a}$
$\underline{a}~\underline{c}~\underline{a}~|~\underline{c}$

or we can add a $b$, which increases the value of $f_1$ by 1:
$\underline{a}~\underline{c}~\underline{a}~|~\underline{b}$

Then I look at an example of a 3-string that does end in $b$, say
$\underline{a}~\underline{c}~\underline{b}$

you can then add an $a$ or a $c$; whichever you choose doesn't affect the number of $f_1$, only $f_0$:
$\underline{a}~\underline{c}~\underline{b}~|~\underline{a\text{ or }c}$

or you can add a $b$ to increase $f_1$ by 1:
$\underline{a}~\underline{c}~\underline{b}~|~\underline{b}$

Is there a clearer way to write the justification if it's not clear enough already? I appreciate the help

9. Apr 23, 2014

### haruspex

That's ok, but it only covers one equation. I would just write out
There are f0(n-1) of length n-1 ending ..x, where is either a or c, etc.
0→0 = ..x → ..xc or ..x→..xa
1→0 = ..b → ..bc
0→1 = ..x → ..xb
1→1 = ..b → ..bb
The first two add up to give the f0(n), the second two to give f1(n).

10. Apr 23, 2014

### SithsNGiggles

Yes thank you I noticed that too as I was writing my answer. Thanks for the help!