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