Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2010-03-29 06:51:02

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)

Offline

#2 2010-03-29 10:12:03

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)

Offline

#3 2010-03-30 01:44:10

White_Owl
Member
Registered: 2010-03-03
Posts: 106

Re: To solve recurrence relations by iterations

Izmael wrote:

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.

Izmael wrote:

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...

Offline

Board footer

Powered by FluxBB