Generating function of a recurrance relation

Click For Summary
SUMMARY

The discussion centers on deriving the generating function A(x) for the recurrence relation a[n+2] = −a[n+1] + 6a[n] with initial conditions a[0] = 2 and a[1] = −1. The correct formula for A(x) is established as A(x) = (2x + 1) / (1 + x - 6x^2). However, the user struggles with obtaining the correct coefficients in the series expansion, indicating a potential error in their calculations or assumptions. The first few terms of the sequence are confirmed as 2, -1, 13, -19, 97, -211.

PREREQUISITES
  • Understanding of generating functions in combinatorics
  • Familiarity with recurrence relations and their solutions
  • Knowledge of Taylor series expansions
  • Basic algebraic manipulation of polynomials
NEXT STEPS
  • Review the derivation of generating functions for linear recurrence relations
  • Practice solving recurrence relations using initial conditions
  • Learn about the implications of series expansions on coefficient extraction
  • Explore advanced techniques in generating functions, such as the use of roots of characteristic equations
USEFUL FOR

Mathematicians, computer scientists, and students studying discrete mathematics or combinatorial theory, particularly those interested in generating functions and recurrence relations.

jrp131191
Messages
17
Reaction score
0
Suppose A(x) is a generating function for the sequence a0, a1, a2, . . . that satisfies
the recurrence a[n+2] = −a[n+1] + 6a[n] for n > 0, with initial conditions a[0] = 2 and
a[1] = −1. Find a formula for A(x) and use it to find an explicit formula for a[n].

I don't know what I am doing wrong, here is what I have done..
the first few terms of this sequence are 2,-1,13,-19,97,-211
my taylor series expansion is .. 1 + x + 5 x^2 + x^3 + 29x^4 which is wrong..

______________________________________…

a[n+2] = −a[n+1] + 6a[n]

all summations for n_> 0

∑ a[n+2] = -∑a[n+1] + 6∑a[n]

∑ a[n+2]x^n = -∑a[n+1]x^n + 6∑a[n]x^n

(1/x^2)∑ a[n+2]x^(n+2) = -(1/x)∑a[n+1]x^(n+1) + 6∑a[n]x^n

A(x) = ∑a[n]x^n

=> (1/x^2)(A(x) - a[0] - a[1]) = -(1/x)(A(x) - a[0]) + 6A(x)

A(x) - a[0] - a[1] = -x(A(x) - a[0]) + 6x^2A(x)

A(x)-2+1 = -xA(x) + 2x + 6x^2A(x)

A(x) +xA(x) - 6x^2A(x) = 2x + 1

A(x)(1+x-6x^2) = 2x+1

A(x) = (2x+1)/(1+x-6x^2)

and this functions series expansion does not have the right coefficients as mentioned before.. i really can't see where I've gone wrong..

help please :(
 
Physics news on Phys.org
jrp131191 said:
A(x)(1+x-6x^2) = 2x+1

A(x) (1 + x - 6x^2) = 2x - 1
 
jrp131191 said:
(1/x^2)∑ a[n+2]x^(n+2) = -(1/x)∑a[n+1]x^(n+1) + 6∑a[n]x^n

A(x) = ∑a[n]x^n

=> (1/x^2)(A(x) - a[0] - a[1]) = -(1/x)(A(x) - a[0]) + 6A(x)

an x is missing from one of the terms above
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 18 ·
Replies
18
Views
3K
  • · Replies 6 ·
Replies
6
Views
5K
  • · Replies 13 ·
Replies
13
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K