Novice in Recurrence Relations

[juki_inla]

I am totally new to this area, and have some major trouble understanding how recurrence relations were derived from the problems, what to do and what's not. Really appreciate any guidance!For example: Give a Ternary String (containing only 0s, 1s, or 2s), we have to find out the recurrence relations of number of ternary string that contains 2 consecutive 0s.

Given solution:
String starting from 1--- a_n-1
String starting from 2--- a_n-1
=2*a_n-1
String starting from 01-- a_n-2
String starting from 02-- a_n-2
=2*a_n-2
String starting from 00-- a_n-2
=3^n-2

a_n= 2*a_n-1 + 2*a_n-2+3^n-2

My troubles are:
1) a_n-1. Can I safely understand it as the previous term we are working with before we get a_n

2) How do we derive these a_n-1, a_n-2 and so on? Until when/which previous terms should I stop?

3) Does that mean that anytime we use the previous terms, the initial condition [whether given or not] we have to assume it is true? For in this case, a_n-1
is working already with a ternary string of 2 consecutive zeros?

Thanks in advance!

 

[gb7nash]

Have you learned about generating functions yet?

 

[gb7nash]

1) a_n-1. Can I safely understand it as the previous term we are working with before we get a_n

Yes. Since in the first and second case you haven't violated any rules and placed a 0 right before the next slot, you can place any arbitary n-1 length valid ternary word, which is:
a_n-1.

2) How do we derive these a_n-1, a_n-2 and so on? Until when/which previous terms should I stop?

There's nothing to derive from here. Once you have the equation, you have the reccurrence formula. You stop when you find all the cases.

3) Does that mean that anytime we use the previous terms, the initial condition [whether given or not] we have to assume it is true? For in this case, a_n-1
is working already with a ternary string of 2 consecutive zeros?

Don't think of a recurrence relation like that. All it's saying is that the number of n-length ternary strings has some relationship with the number of (n-1)-length, and (n-2)-length ternary strings. You're not fixing a particular string. Obviously though, this only works for n>2, since a₀ is undefined according to your problem.

Now to the actual problem...

Given solution:
String starting from 1--- a_n-1
String starting from 2--- a_n-1
=2*a_n-1
String starting from 01-- a_n-2
String starting from 02-- a_n-2
=2*a_n-2
String starting from 00-- a_n-2=3^n-2

a_n= 2*a_n-1 + 2*a_n-2+3^n-2

The first two look fine. However, the last one is not. You cannot follow 00 with an arbitrary valid ternary string. For instance, if you allow this, you can have 000_______, which is not valid. Try creating subcases for 00 and let's see what you get.

P.S. The way I interpreted the problem was that a valid word has only 1 pair of consecutive zero's, and no other rules. If this assumption is false, let me know.

 

[juki_inla]

1) a_n-1. Can I safely understand it as the previous term we are working with before we get a_n

Yes. Since in the first and second case you haven't violated any rules and placed a 0 right before the next slot, you can place any arbitary n-1 length valid ternary word, which is:
a_n-1.

2) How do we derive these a_n-1, a_n-2 and so on? Until when/which previous terms should I stop?

There's nothing to derive from here. Once you have the equation, you have the reccurrence formula. You stop when you find all the cases.

3) Does that mean that anytime we use the previous terms, the initial condition [whether given or not] we have to assume it is true? For in this case, a_n-1
is working already with a ternary string of 2 consecutive zeros?

Don't think of a recurrence relation like that. All it's saying is that the number of n-length ternary strings has some relationship with the number of (n-1)-length, and (n-2)-length ternary strings. You're not fixing a particular string. Obviously though, this only works for n>2, since a₀ is undefined according to your problem.

Now to the actual problem...


The first two look fine. However, the last one is not. You cannot follow 00 with an arbitrary valid ternary string. For instance, if you allow this, you can have 000_______, which is not valid. Try creating subcases for 00 and let's see what you get.

P.S. The way I interpreted the problem was that a valid word has only 1 pair of consecutive zero's, and no other rules. If this assumption is false, let me know.

Wow, thanks for the reply!

Nope, have not learned generating functions before.

If I am not wrong, the problem allow for string as long as there were 2 consecutive zeros.

However, let me try to apply what I had understand based on your assumptions

If only 1 pair of consecutive zeros is allowed in the string,

We should have the only following cases:

a_n-3: 001, 002 = 2a_n-3
a_n-4: 1001, 1002, 2001, 2002 = 4a_n-4

a_n = 2a_n-1 + 2a_n-2 + 2a_n-3 + 4a_n-4

Will that be correct?

 

[gb7nash]

If I am not wrong, the problem allow for string as long as there were 2 consecutive zeros.

You might want to verify with your professor what it is. I was thinking about this problem somemore and depending on what it is, the problem can be easy or hard.

For example:

If the assumption is that you can have 1 pair of adjacent 0's and no other zeros anywhere, then the problem isn't that hard. e.g. 100231 is valid while 100203 is not.

If the assumption is that you can have any number of zeros, as long as one pair of adjacent zeros exist, then the problem isn't that hard either. e.g. 0000000 is valid.

If the assumption is that you can only have 1 pair of adjacent zeros, but can allow other zeros as long as they're not adjacent, then the problem is a bit more difficult. e.g. 00102320 is valid while 002003 is not.

I can't tell which one it is and I don't want to lead you the wrong way. If someone knows, I'm all ears.