Re: Recurrence Relation to Closed Form
[ QUOTE ]
I guess I'm asking, what is the standard procedure that can take me from the recurrence relation to the closed form solution? Is there a straightforward methodology? Or is this usually done on a case-by-case basis?
[/ QUOTE ]
Given the recurrence, start at n=0 (or =1, or whatever is appropriate for the problem) and write out the values of f(n) only as a function of n (i.e. substituting the value of f(n-1) appropriately) and look for a pattern. This can take a lot of paper, and might not work in all cases. Then try to prove your pattern inductively: assume it's true for n-1, prove it for n. Other than that, yes it's case-by-case.
You are, presumably, initializing f(1) = 1.
Then
f(2) = [1] [(3)(4)/2]
f(3) = [1] [(3)(4)/2] [(5)(6)/2]
f(4) = [1] [(3)(4)/2] [(5)(6)/2] [(7)(8)/2]
...
Look how clear it is that you are multiplying all the numbers 3,4,5,6,7,8,etc. Clean it up by throwing in a 2/2 term in front, and you have (2n)! practically jumping off the page at you. Even easier is the 1/2^n factor. You're done.
alThor
|