Recurrence relation involving multiple sequences

In summary, the conversation discusses a recursive sequence with initial terms ##f_0(0)=1##, ##f_1(0)=0##, ##f_0(1)=2##, and ##f_1(1)=1##, and asks to justify the recursive relations ##f_0(n)=2f_0(n-1)+f_1(n-1)## and ##f_1(n)=f_0(n-1)+f_1(n-1)##. The conversation also mentions the context of the sequence, which involves strings of length ##n## made up of the letters ##a,b,c## that do not contain the sequence ##ba##. The number of strings ending in a
  • #1
SithsNGiggles
186
0

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?
 
Physics news on Phys.org
  • #2
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
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
SithsNGiggles said:

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


SithsNGiggles said:
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.
 
  • Like
Likes 1 person
  • #5
pasmith said:
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
 
  • #6
SithsNGiggles said:
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.
 
  • Like
Likes 1 person
  • #7
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
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
SithsNGiggles said:
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 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).
 
  • Like
Likes 1 person
  • #10
Yes thank you I noticed that too as I was writing my answer. Thanks for the help!
 

Related to Recurrence relation involving multiple sequences

1. What is a recurrence relation involving multiple sequences?

A recurrence relation involving multiple sequences is a mathematical formula that describes how a sequence of multiple variables is related to each other. It is a way of expressing the relationship between the current term of a sequence and previous terms in the same or different sequences.

2. How is a recurrence relation involving multiple sequences useful?

Recurrence relations involving multiple sequences are useful in solving complex mathematical problems, such as in combinatorics, probability, and number theory. They also have applications in computer science and engineering, particularly in algorithm design and optimization.

3. What is the difference between a single sequence recurrence relation and a multiple sequence recurrence relation?

A single sequence recurrence relation involves only one variable in the sequence, while a multiple sequence recurrence relation involves two or more variables in the sequence. In other words, a single sequence recurrence relation describes the relationship between consecutive terms in a single sequence, while a multiple sequence recurrence relation describes the relationship between terms in different sequences.

4. How do you solve a recurrence relation involving multiple sequences?

To solve a recurrence relation involving multiple sequences, you can use various techniques such as substitution, iteration, and generating functions. It is also helpful to have a good understanding of algebra and combinatorics to properly manipulate the equations and solve for the desired variables.

5. Can recurrence relations involving multiple sequences be applied to real-world problems?

Yes, recurrence relations involving multiple sequences can be applied to real-world problems. For example, they can be used to model population growth, analyze stock market trends, and optimize resource allocation in industries. These relations allow us to make predictions and solve problems that involve multiple variables and their relationships.

Similar threads

Replies
2
Views
740
  • Quantum Interpretations and Foundations
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
895
  • Calculus and Beyond Homework Help
Replies
1
Views
552
  • Calculus and Beyond Homework Help
Replies
1
Views
375
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
34
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top