Results 1 to 2 of 2

Thread: Recursive relation

  1. #1
    Senior Member
    Apr 2009

    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 $\displaystyle q_n$ be the number of nonnegative ordered pairs which solve $\displaystyle 2a+5b = n$.

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

    Now $\displaystyle 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, $\displaystyle A(x)B(x)$ is the generating function sequence for the sequence $\displaystyle q_1, q_2, q_3, \cdots $

    $\displaystyle 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$

    $\displaystyle \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 $\displaystyle q_1=q_3 = 0$ and $\displaystyle 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 $\displaystyle q_n $

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

  2. #2
    Senior Member
    Apr 2009
    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: Dec 6th 2011, 09:25 AM
  2. Replies: 1
    Last Post: Apr 6th 2011, 11:46 PM
  3. Replies: 4
    Last Post: Apr 27th 2010, 07:57 AM
  4. Replies: 1
    Last Post: Mar 1st 2010, 07:24 AM
  5. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 29th 2009, 07:32 AM

Search Tags

/mathhelpforum @mathhelpforum