Thread: Recurrence equations

Hi.

Could you help me solve these equations? I know how to solve recurrence equations with only [tex]a_k[\tex] and scalars in, and sometimes I can also guess the formula and then prove it by induction. But I have no idea how to go about solving these:


1)

2)

3)

4)

5)

6)

7)

And two problems:

1)Find the number of strings length n consisting of numbers 0,1,2 where the following bits differ at most 1. What I mean is that such strins should look like that: 00000000111111222222222111111100000001111110000000 011111000001111122222111
I've tried to find a recurrence pattern(if we begin with 0, then after the 0s we can only put 1s, but after 1s there can be 0s or 2s, but then after 0s and 2s there can be only 1s and there we go again) but I have no idea how to write such a recurrence since there can be any number of 1s,2s 0s used.

2) similar, only this time we form bit strings using numbers 0, 1, 2, 3 and we need to find the number of strings in which 0 and 1 are not next to each other.

Please help.

Hey wilhelm.

You should show us everything you have tried and any brainstorming you have had for these problems to get specific and more importantly, useful feedback.

Well, I have already solved the 1st and 2nd equations, using and but I do not know what to do to "get rid of" or . Putting in doesn't help. What should I use. As to the first text problem, I have already written what I've tried doing. I'd be really grateful for some hint on solving these problems or maybe you could recommend a good book in which recurrence equations are nicely explained.

Generally the way to solve general recurrence equations is to expand the relation by getting a_n in terms of an expression with only n's in them (usually a series, a multiplication, or something like that) and then classify the series in a way that gives a solution.

This is how to solve the general case of recurrence relations and what mathematicians try and do is find a pattern for n terms where any simplification that can be done is done and any that isn't is just left in the best simplification form.

This is the general case, but I did find a PDF that covers some specifics that include the classes of problems you have:

http://rutherglen.science.mq.edu.au/...older/dm16.pdf