Results 1 to 3 of 3

Math Help - Proving Generating Functions

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    14

    Proving Generating Functions

    Let an denote the solutions of n = x1 + x2 where x1, x2 are natural numbers and x2 is an even number.

    I need to show that the generating function of an is of the form:
    (1 + x + x^2 + x^3 + ...)(1 + x^2 + x^4 + x^6 + ...) = 1/[(1-x)(1-x^2)]

    I ultimately want to find a closed formula for an. However I would like to prove the above first before I go about doing that. Any ideas would be great. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2010
    From
    Rez
    Posts
    21
    So a_n is the *number* of solutions to n = x_1 + x_2? Are x_1 and x_2 distinct? For example for a_6, are 6=4+2 and 6=2+4 two separate solutions, so a_6 = 2, or is a_6 = 1?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by mathmaniac234 View Post
    Let an denote the solutions of n = x1 + x2 where x1, x2 are natural numbers and x2 is an even number.

    I need to show that the generating function of an is of the form:
    (1 + x + x^2 + x^3 + ...)(1 + x^2 + x^4 + x^6 + ...) = 1/[(1-x)(1-x^2)]

    I ultimately want to find a closed formula for an. However I would like to prove the above first before I go about doing that. Any ideas would be great. Thanks!
    Hi mathmaniac,

    You just have to think about the coefficient of x^n in the product
    (1 + x + x^2 + x^3 + \dots)(1 + x^2 + x^4 + x^6 + \dots).
    In order to get an x^n, you need one term from
    1 + x + x^2 + x^3 + \dots
    which can be any power of x, say x^i
    and one term from
    1 + x^2 + x^4 + x^6 + \dots
    which can be any even power of x, say x^{2j}.
    Then you must have x^i \cdot x^{2j} = x^n,
    i.e.
    i + 2j = n.

    The number of solutions to this equation is the coefficient of x^n in the product.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2010, 05:46 PM
  2. Generating functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 14th 2009, 10:23 AM
  3. Generating functions
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 8th 2009, 11:50 AM
  4. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2008, 05:43 PM
  5. Generating functions...need some help here
    Posted in the Calculus Forum
    Replies: 4
    Last Post: January 31st 2008, 05:32 PM

Search Tags


/mathhelpforum @mathhelpforum