Recurrence relation involving multiple sequences

[SithsNGiggles]

Homework Statement

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}##

Homework 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)##.

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?

 

[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 f₀ and f₁ supposed to refer to ending in a particular one of the three letters?

 

[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##.

 

[pasmith]

Homework Statement

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}##

Homework Equations

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##.

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

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,

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.

You are in effect asked to show that if the number of strings of length [itex]n-1[/itex] which don't end in 'b' is [itex]f_0(n-1)[/itex] and the number of strings of length [itex]n-1[/itex] which do end in 'b' is [itex]f_1(n-1)[/itex], then the number of strings of length [itex]n[/itex] which don't end in 'b' is [tex]
f_0(n)=2f_0(n-1)+f_1(n-1) [/tex] and the number of strings of length [itex]n[/itex] which do end in 'b' is [tex]
f_1(n)=f_0(n-1)+f_1(n-1).
[/tex] 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 [tex]
\begin{pmatrix} f_0(n) \\ f_1(n) \end{pmatrix} =
A\mathbf{v}_1\lambda_1^n + B\mathbf{v}_2\lambda_2^n[/tex] where [itex]\lambda_1[/itex] and [itex]\lambda_2[/itex] are the eigenvalues of [tex]
\begin{pmatrix}
2 & 1 \\ 1 & 1
\end{pmatrix}[/tex] with corresponding eigenvectors [itex]\mathbf{v}_1[/itex], [itex]\mathbf{v}_2[/itex] and [itex]A[/itex] and [itex]B[/itex] are constants determined by the initial conditions.

 

[SithsNGiggles]

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

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.

You are in effect asked to show that if the number of strings of length [itex]n-1[/itex] which don't end in 'b' is [itex]f_0(n-1)[/itex] and the number of strings of length [itex]n-1[/itex] which do end in 'b' is [itex]f_1(n-1)[/itex], then the number of strings of length [itex]n[/itex] which don't end in 'b' is [tex]
f_0(n)=2f_0(n-1)+f_1(n-1) [/tex] and the number of strings of length [itex]n[/itex] which do end in 'b' is [tex]
f_1(n)=f_0(n-1)+f_1(n-1).
[/tex] 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 [tex]
\begin{pmatrix} f_0(n) \\ f_1(n) \end{pmatrix} =
A\mathbf{v}_1\lambda_1^n + B\mathbf{v}_2\lambda_2^n[/tex] where [itex]\lambda_1[/itex] and [itex]\lambda_2[/itex] are the eigenvalues of [tex]
\begin{pmatrix}
2 & 1 \\ 1 & 1
\end{pmatrix}[/tex] with corresponding eigenvectors [itex]\mathbf{v}_1[/itex], [itex]\mathbf{v}_2[/itex] and [itex]A[/itex] and [itex]B[/itex] are constants determined by the initial conditions.

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.

Thanks for the reply

 

[haruspex]

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##?

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

 

[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!

 

[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

 

[haruspex]

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##.

That's ok, but it only covers one equation. I would just write out
There are f₀(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 f₀(n), the second two to give f₁(n).

 

[SithsNGiggles]

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