• Support PF! Buy your school textbooks, materials and every day products Here!

Generating Function

  • Thread starter Punkyc7
  • Start date
  • #1
420
0
Find the OGF for the recurrence

a[itex]_{n}[/itex]= 6 * a[itex]_{n-1}[/itex]+ a[itex]_{n-2}[/itex] a[itex]_{0}[/itex]=2, a[itex]_{1}[/itex]=1



So here is what I did

I said let A = [itex]\sum[/itex][itex]_{2>=n} [/itex]a[itex]_{n}[/itex]x[itex]^{n}[/itex]


then I got

A = 6x (A+x) + x[itex]^{2}[/itex](A +x+2)

which gets me

A= [itex]\frac{6x^2+x^{3} +2x}{1-6x - x^2}[/itex]



ButI should get [itex]\frac{2-x}{1-6x - x^2}[/itex]


Can any one tell me what I am doing wrong ?
 

Answers and Replies

  • #2
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,302
998
Find the OGF for the recurrence

a[itex]_{n}[/itex]= 6 * a[itex]_{n-1}[/itex]+ a[itex]_{n-2}[/itex] a[itex]_{0}[/itex]=2, a[itex]_{1}[/itex]=1

So here is what I did

I said let A = [itex]\sum[/itex][itex]_{2>=n} [/itex]a[itex]_{n}[/itex]x[itex]^{n}[/itex]

then I got

A = 6x (A+x) + x[itex]^{2}[/itex](A +x+2)  = A(6x) + 6x2 + A(x2) + x3 +2x2
This gets you a different A.
which gets me

A= [itex]\frac{6x^2+x^{3} +2x}{1-6x - x^2}[/itex]

ButI should get [itex]\frac{2-x}{1-6x - x^2}[/itex]

Can any one tell me what I am doing wrong ?
Congrats on your 400th post ! :smile:
 
  • #3
420
0
Thank you on the congratulations. But I do not see how that get me a different A. Did I define what A is right. Usually the generating function start at zero but with this problem that gives you bad subscripts.
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
Find the OGF for the recurrence

a[itex]_{n}[/itex]= 6 * a[itex]_{n-1}[/itex]+ a[itex]_{n-2}[/itex] a[itex]_{0}[/itex]=2, a[itex]_{1}[/itex]=1



So here is what I did

I said let A = [itex]\sum[/itex][itex]_{2>=n} [/itex]a[itex]_{n}[/itex]x[itex]^{n}[/itex]


then I got

A = 6x (A+x) + x[itex]^{2}[/itex](A +x+2)

which gets me

A= [itex]\frac{6x^2+x^{3} +2x}{1-6x - x^2}[/itex]



ButI should get [itex]\frac{2-x}{1-6x - x^2}[/itex]


Can any one tell me what I am doing wrong ?
I usually find it safer, to write things out a bit more:
[tex] A = a_2 x^2 + a_3 x^3 + a_4 x^4 + \cdots = (6a_1 + a_0)x^2
+ (6a_2 + a_1)x^3 + (6a_3 + a_2)x^4 + \cdots\\
= (6+2)x^2 + x^3 + 6x A + x^2 A = x^3 + 8x^2 + (x^2 + 6x)A.[/tex]
This will give you a different A from what you obtained.

Besides that difference, maybe the answer was for a GF starting at a_0*x^0, or at a_1*x^1. However, I checked that, and could not get the posted answer for any three variants of the problem. Just to be sure, I used Maple to get a solution, and got an answer in agreement with a_0 + a_1 x + A. Here is the Maple command, but I won't give the output, since that would deprive you of the fun of getting it yourself.
> rsolve({a(n)=6*a(n-1)+a(n-2),a(1)=1,a(0)=2},a,'genfunc'(x));

RGV
 

Related Threads on Generating Function

  • Last Post
Replies
4
Views
878
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
2
Views
817
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
816
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
4K
Top