Recursive relation

**usagi_killer** · July 20th 2010, 10:37 AM

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!

**usagi_killer** · July 20th 2010, 10:59 PM

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.

Thread: Recursive relation

LinkBack

Thread Tools

Display

Recursive relation

Similar Math Help Forum Discussions

Is this relation recursive?

For the following relation, show that R is an equivalence relation and determine the.

A recursive relation table and proving problem...

Decide whether or not the relation is an equivalent relation. Help please?

Primitive Recursive vs Recursive Functions

Search Tags