Formal power series and non/homogeneous recurrence relations

  • Thread starter Ian_Brooks
  • Start date
  • #1
128
0

Homework Statement



20104302321196340826647900012504568.jpg


Homework Equations




We're using generating functions, and recurrence relations of homogeneous and non-homogeneous types

The mark allocation is 2, 3, 3 and 2


The Attempt at a Solution



I think I've done the first part correctly. The closed form is in terms of z, right? I get:

F(z) = z / (1 - z - z2)

but I'm unsure if I have to go into partial fractions for this in my answer. For part b, I get:

A(z)(1 - 2z + z2) = a0 + z(a1 - 2a0) ...
= F(z)
so I take my closed formula from part a and substitute F(z) for it so I get

A(z) = z / [ (1 - z - z2) (1-z)2) ]

I'm still unsure if this is right, since looking at previous examples, they express A(z) in terms of itself, that is: group together coefficients of an etc. and get a more complex remainder; They suggest to do this:

A(z)(1 - 2z + z2) = a0 + z (a1 - 2a0) + z2 (a2 -2a1 + a0) ...

and group together the coefficients of a1 or a2 etc. so there is a generating function within the brackets. I used F(z) in this case, but is that really in terms of itself?

For part (c), I want to use the bn and pn way for non homogeneous recurrence relations, but I got lost; we've only gone over the pn being a power of n (n2, n or even just integers) but the function here, even in the explicit form, is an integer to the power of n (I solved the Fibonacci sequence via the polynomial method). I used the partial fraction method, but it ended up very ugly, substituting alpha for (1 - root5 / 2) and beta for (1 - alpha), their product as negative 1, and their sum as positive 1. This is only a three mark question, and my working is over 3 pages, incomplete. Even if I finish it, I don't remember how to get from the closed form to explicit (that's in terms of n, right?). I can use a/(1-bz) = a times bn , but what about with multiple powers of (1-z) at the denominator? I only recall the generating function version of that ([tex]\sum[/tex] (n+k)Ck z2 ) (bounds from n=0 to infinity), but not in it's explicit form.

Then for part (d), I'm unsure how to use part (c) to calculate the sum as I am completely lost for it. Any pointers?
 

Answers and Replies

  • #2
lanedance
Homework Helper
3,304
2
i'd agree with a) & b) and think you're essentially doing the same thing as the solution

for d) try writing out an in terms of the Fj's and see if you can spot a pattern
 
Last edited:
  • #3
lanedance
Homework Helper
3,304
2
for c) you want to try and probably get rid of the F term so how about looking at
[tex] a_{n+1}-a_n{n} [/tex]

after manipulation, this should leave you with an equation with a negative F term. Then adding that to the original, with correct choice of index, should leave you with a pure recurrence relation of aj that may be easier to solve...
 

Related Threads on Formal power series and non/homogeneous recurrence relations

  • Last Post
Replies
2
Views
8K
  • Last Post
Replies
2
Views
1K
Replies
1
Views
1K
Replies
0
Views
2K
Replies
2
Views
3K
Replies
8
Views
3K
Replies
7
Views
4K
  • Last Post
Replies
0
Views
1K
Replies
4
Views
7K
Replies
1
Views
2K
Top