I was looking to figure out how to solve the following:
The recurrence relation:
Given:
How would you go about solving this in terms of a generating function?
Thanks!
Kev
Hello, Kev!
This one requires another trick . . .
The recurrence relation: . .[1]
Given: .
Consider the case: . .[2]
. . . . . . Multiply [1] by 4: . . .[3]
Subtract [3] from [2]: .
. . . . .
Let
Divide by
. . which factors; .
. . and has roots: .
. . . . . .Go for it!
I haven't thought about recurrences and GF since college. This is an interesting topic. Here is an example of one I solved years ago. I still had the paper. I keep running into problems with the one posted. Something small I'm overlooking. Most always is. Maybe this will give you something to go by.
Anyway, here's an example of a recurrence using GF
Let y=A(x):
Notice the familiar geometric series solution in the PFD,
This gives us
Hope this helps. I can easily get the result from Maple, but that's no fun.
Hello, Kev ... and anyone else interested,
Thought I'd show how I crank out the recursion function.
In the above problem, we had roots: .
. . where the base of exponential terms.
We now construct the function.
It contains: and
And because the 2 is repeated, we have the term: .
The function has the form: .
. . and we must determine
We use the first two terms of the sequence: .
. . and we can calculate the third term: .
So we have:
Divide [3] by -4: .
. . . . . . Add [2]: .
And we get: .
Substitute into [1]: .
Substitute into [2]: .
The function is: .
. .
Factor: .
If you would be so kind...
I'm trying to run the original question through this method and I'm running into some trouble. I know I can avoid this by using Soroban's trick of putting the recursion into a form that removes the term, but can this be done from the original problem itself?
I'm probably being confusing. I'll just post this:
Define a series
Then
The last term is giving me problems. All I can think of to do with it is to cast it in the form
But when I complete the steps of the method to find an equation for A(x) I get
Assuming I have everything else right, I'm still stuck with that A(4x) term. Any thoughts?
-Dan
That is the same exact snag I run into, TQ.
I thought about leaving A(4x)=4y.
Solving for y and using PFD, results in
I don't beleive that gets us anywhere, though?.
Alas, I am at work and don't have much time. I will try to take a glance this evening.
Hey. This is #1000. I am now a contributor, as Janvdl reminded me.
With that A(4x), I was grabbing at straws. There's something to be done with that 4^n, I just don't know for sure what it is. I have never tackled any like that. If you figure it out, please let me know. I will surely reciprocate if I get lucky.
Perhaps a search regarding generating functions and recurrence relations may prove fruitful.