0

I know similar questions have been asked before and I've had a look through them but I'm still struggling to understand, so please bear with me.

The question asks you to find a recurrence relation for A of n.

Solution to the question

I'm not making the connection between the first sentence in either case and how this implies that this is equal to the number of strings in the previous term(s); n - 1 and n - 2.

This a question from an assignment for a Discrete Maths paper.

Erik Murthy
  • 1
  • I suggest you use only digits $0,1,2$ and list the possibilities by hand for strings up to length $3$. Adding $3$ and $4$ as acceptable digits will only change a constant in the recurrence. Watch how the strings of length $n$ are formed from the shorter strings. – Ross Millikan Jun 09 '18 at 05:32

1 Answers1

1

In the first case, there is a one to one map between the strings contributing to $a_n$ not starting with $0$ but with another fixed number say $1$ and the strings contributing to $a_{n-1}$. That is, every string contributing to $a_{n-1}$ gives a string contributing to $a_n$ by appending a $1$ at the left end, and vice versa. Since we can do this for all of $1,2,3,4$, we get a factor of $4$.

In the second case, there is a one-one correspondence between the strings contributing to $a_n$ beginning with $0$ and having a fixed second digit (say $1$) and the strings contributing to $a_{n-2}$. Specifically, given a string contributing to $a_n$ starting with $01$, it corresponds to the string formed by its last $n-2$ letters. Since we could have any of $1,2,3,4$ instead of $1$, there is again a factor of $4$.

Manan
  • 1,596