Math Is Fun Forum

White_Owl

Member

Registered: 2010-03-03

Posts: 106

To solve recurrence relations by iterations

I have a recurrence relation:

So I am trying to write an iterative equation:

If I understand correctly, at the end I should get an expression from

, but how?

Just by looking at the iteration steps and some playing around I came up with the equation:

But I do not understand what is the 'correct' way of finding that equation?

Last edited by White_Owl (2010-03-29 06:52:32)

Izmael

Member

Registered: 2010-03-28

Posts: 4

Re: To solve recurrence relations by iterations

Hello,

I don't understand, what you want to solve. I assume that you want to find an explicit formula for your reccurence.

Then we have

Now, we can prove this by induction. First step is for k=1. This trivially holds. Assume correctness for k = n.

Now we need to prove the identity

That's easy. Try it.

Izmael

Last edited by Izmael (2010-03-29 10:12:42)

White_Owl

Member

Registered: 2010-03-03

Posts: 106

Re: To solve recurrence relations by iterations

I don't understand, what you want to solve. I assume that you want to find an explicit formula for your reccurence.

Yes. I work with Rosen's book "Discrete Mathematics and Its Applications"; in it the wording of the problem is "to solve the recurrence". But yes, the task is actually to convert a recurrence form into a normal function.

Then we have

I see one difference in our approaches: you went backward (or forward?) starting from the

, not from

as was suggested by my textbook... hmm...