Results 1 to 2 of 2

Math Help - Recursive relation

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    306

    Recursive relation

    Find a recursive relation for the number of distinct ordered pairs (a,b) of non-negative integers satisfying 2a+5b=100.

    Okay, so I took an entirely different approach to this question using generating functions unlike my book. However I am stuck at the end. Any assistance to finish it off would be highly appreciated!

    Let q_n be the number of nonnegative ordered pairs which solve 2a+5b = n.

    We define  A(x) = 1+x^2+x^4+x^6+ \cdots and B(x) = 1+x^5+x^{10}+x^{15} + \cdots

    Now A(x)B(x) = \left(1+x^2+x^4+x^6+ \cdots\right)\left(1+x^5+x^{10}+x^{15} + \cdots\right) = 1+x^2+x^4+x^5+x^6 + \cdots

    Clearly, A(x)B(x) is the generating function sequence for the sequence q_1, q_2, q_3, \cdots

    A(x)B(x) = \left(\frac{1}{1-x^2}\right)\left(\frac{1}{1-x^5}\right) = q_0+q_1x+q_2x^2+q_3x^3+q_4x^4 + \cdots

    \implies 1 = (1-x^2)(1-x^5)\left(q_0+q_1x+q_2x^2+q_3x^3+q_4x^4 + \cdots\right)

    We can see from inspection that q_1=q_3 = 0 and q_2=q_4=q_5=q_6 = 1

    But up to this step, I have no idea how to get the recursive relation for q_n

    Many thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    Posts
    306
    Haha, Nvm seems like I'll answer my own question -_-, expand the RHS and equate the coefficients for x^k, k =>7 and the recurrence pattern comes up nicely.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is this relation recursive?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 6th 2011, 09:25 AM
  2. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  3. Replies: 4
    Last Post: April 27th 2010, 07:57 AM
  4. Replies: 1
    Last Post: March 1st 2010, 07:24 AM
  5. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 07:32 AM

Search Tags


/mathhelpforum @mathhelpforum