5
$\begingroup$

Let's denote $h_n$ as the number of soulutions of the following equation:

$$ 2x_1 + 4x_2 = n$$

where $x_i \in \mathbb N$.

Find generating function of the sequence $h_n$ and calculate $h_{2000}$.

I've found the generating function:

$$\frac{1}{1-x^2}\cdot \frac{1}{1-x^4},$$ but I don't know how to expand it now. Any ideas?

$\endgroup$
  • $\begingroup$ first of all $n$ is even ,alternate form is $x_1+2*x=k$ where $k=n/2$ now that equation has infinite solution,because there is not constrant that $k$ should be even $\endgroup$ – dato datuashvili Apr 3 '13 at 18:15
  • $\begingroup$ what kind of notation is $N$? $\endgroup$ – dato datuashvili Apr 3 '13 at 18:17
  • $\begingroup$ $N$ is natural. Sorry, maybe I should have used another notation. $\endgroup$ – JosephConrad Apr 3 '13 at 18:18
  • $\begingroup$ use $Z$ for integers or $Z+$ for positive intergers no problems btw $\endgroup$ – dato datuashvili Apr 3 '13 at 18:20
  • 2
    $\begingroup$ @dato: $n$ is variable. For a given value of $n$, the number $h_n$ (as a function of $n$) is the number of solutions to $2x_1 + 4x_2 = n$ (for that $n$). $\endgroup$ – ShreevatsaR Apr 3 '13 at 18:27
6
$\begingroup$

As you observed, if the generating function for $h_n$ is $$f(x) = h_0 + h_1x + h_2x^2 + h_3x^3 + \dots + h_nx^n + \dots,$$ then $$f(x) = (1 + x^2 + x^4 + x^6 + \dots)(1 + x^4 + x^8 + x^{12} + \dots) = \frac{1}{1-x^2}\frac{1}{1-x^4}$$

To actually get the coefficients of $x^n$ in the above, we resort to partial fractions. The denominator of the above can be factored into irreducible factors, using the identity $1-y^2 = (1+y)(1-y)$, as $(1+x)(1-x)(1+x^2)(1+x)(1-x) = (1+x)^2(1-x)^2(1+x^2)$. Therefore, by the general theory of partial fractions, $f(x)$ can be written as $$f(x) = \frac{A}{1+x\vphantom{(1+x)^2}} + \frac{B}{(1+x)^2} + \frac{C}{1-x\vphantom{(1-x)^2}} + \frac{D}{(1-x)^2} + \frac{Ex + F}{1+x^2} + \frac{Gx + H}{(1+x^2)^2}$$ where $A, B, C, D, E, F, G, H$ are constants. Using various painful tricks it's possible to determine the constants, but because I'm not the one doing this as homework, I'll just turn to Wolfram Alpha which says that $$f(x) = \frac{1}{4(1+x)} + \frac{1}{8(1+x)^2} + \frac{1}{4(1-x)} + \frac{1}{8(1-x)^2} + \frac{1}{4(1+x^2)}.$$

Here the five terms are, respectively, $\frac14 \sum_n{(-1)^n x^n}$ and $\frac18 \sum_n {(-1)^n (n+1)x^n}$ and $\frac14 \sum_n x^n$ and $\frac18 \sum_n (n+1)x^n$ and $\frac14 \sum_n{(-1)^n x^{2n}}$, so $$h_{2000} = \frac14 (-1)^{2000} + \frac18 (-1)^{2000}2001 + \frac14 + \frac18 2001 + \frac14 (-1)^{1000} = 501.$$

[That's the answer, but as you can see the whole thing is a quite painful process that I wouldn't wish on my worst enemy, which is why I keep saying that generating functions are not the best way to solve these counting problems, despite the dazzle of the first step where you get some cute expression for the generating function.]


Edit: Just for contrast, the solution without generating functions: Clearly $n$ must be even, so we're counting solutions to $x + 2y = n/2$ in the nonnegative integers. From $0 \le 2y \le n/2$ we have $0 \le y \le \left\lfloor \frac{n/2}{2} \right\rfloor$, and for each such $y$ there is a unique $x = n/2 - 2y$ as solution. So the number of solutions (for even $n$) is $1 + \left\lfloor \frac{n/2}{2} \right\rfloor$, which for $n = 2000$ is $1 + \left\lfloor \frac{1000}{2} \right\rfloor = 501$.

The solution without generating functions is not always this simple, but I think this is a good example of how going down the generating functions route can be a bad idea if you want exact numbers (as opposed to asymptotic estimates, say).

$\endgroup$
  • $\begingroup$ for instance,using some exmaple of variable $n$ we may see some dependence or relationship between number of solutions of each $n$ $\endgroup$ – dato datuashvili Apr 3 '13 at 19:04
  • $\begingroup$ Yes, that case using generating function is not required, but the point is to prepare for my mid-term test:) All in all, thanks a lot for your response! $\endgroup$ – JosephConrad Apr 3 '13 at 20:52
  • $\begingroup$ Regarding your bracketed comment, and aside from the conceptual interest of GFs, do you have any opinion as to the "validity" of directly using a computer simulation for counting problems, such as in this post, vis-a-vis going through the math exercise of producing the GF, and eventually resorting to Mathematica? $\endgroup$ – Antoni Parellada Jan 30 '18 at 16:15
  • $\begingroup$ @AntoniParellada Depends on what you mean by a computer simulation. If you write a program that counts exactly, then (assuming the program has no bugs) you can say your answer is valid, though ideally you'd get independent confirmation by someone else writing a different program that uses a different approach. $\endgroup$ – ShreevatsaR Jan 30 '18 at 16:49
  • 1
    $\begingroup$ @AntoniParellada Then I guess you need to do the probability analysis, until you have something like “with probability 93%, the error is at most 0.5%” or whatever. (Basically you need to know how many times you need to run your simulation until you're reasonably confident the answer is reasonably accurate.) At that point it might end up being easier to do the actual analysis. :-) $\endgroup$ – ShreevatsaR Jan 30 '18 at 17:15
2
$\begingroup$

So assuming your generating function is correct we can see that: $$\frac{1}{1-x^2}=\sum_{n=0}^\infty a_nx^n,\ a_n = \text{ 1 if 2 divides $n$, 0 otherwise}$$

$$\frac{1}{1-x^4}=\sum_{n=0}^\infty b_nx^n,\ b_n = \text{ 1 if 4 divides $n$, 0 otherwise}$$

So we can use this to calculate the product:

$$\frac{1}{1-x^2}\cdot \frac{1}{1-x^4}=\sum_{n=0}^\infty c_nx^n$$

Where $c_n=\sum_{k=0}^n a_kb_{n-k}$, we can see $a_kb_{n-k} = $ 1 if 2 divides $k$ and 4 divides $n-k$, 0 otherwise. We can see that for odd $n$ this always evaluates to 0 (sanity check: this makes sense!), and for even $n$ we have 1 only when $n-k$ is divisible by 4. So for even $c_n$ is simply the number of $0\leq k\leq n$ such that $n-k$ is divisible by 4. With a little bit of thought we can see that this is $\lfloor \frac n 4 \rfloor +1$.

So putting in $n=2000$ gives us 501!

$\endgroup$
  • $\begingroup$ i did not understand one think.why it should be polynomials?and also we can we determine which polynomial will be relevant? $\endgroup$ – dato datuashvili Apr 3 '13 at 19:19
  • $\begingroup$ This solution, BTW, is equivalent to forgetting about generating functions and doing it by hand: let $a_n = [n\text{ is $2x_1$ for some $x_1$}]$ and $b_n = [n\text{ is $4x_2$ for some $x_2$}]$, then they are $a_n = [2|n]$ and $b_n = [4|n]$ respectively as you got, and the number of solutions to $n = 2x_1 + 4x_2$ is $\sum_{k=0}^{n}a_kb_{n-k}$ and the rest as in your paragraph. :-) $\endgroup$ – ShreevatsaR Apr 3 '13 at 19:21
  • $\begingroup$ This solution relies fairly heavily on the use of generating functions (formal power series), they're a bit tricky to get used to, and so I recommend the free book generatingfunctionology by Herbert Wilf: math.upenn.edu/~wilf/DownldGF.html $\endgroup$ – Alex J Best Apr 3 '13 at 19:23
  • $\begingroup$ @ShreevatsaR Yeah generating functions are pretty useful, but I guess in this case totally unnecessary! $\endgroup$ – Alex J Best Apr 3 '13 at 19:46
  • $\begingroup$ @AlexJBest I wish I could accept also your answer. Thanks a lot! $\endgroup$ – JosephConrad Apr 3 '13 at 20:52
0
$\begingroup$

let us think n as following variables

$n=6$

only one solution $x_1=1$ and $x_2=1$

$n=8$

again one solution

$x_1=2$ and $x_2=1$

$n=10$

now we have following solutions

$x_1=3$ and $x_2=1$,second pair would be $x_1=1$ and $x_2=2$

now take $n=12$

$x_1=4$ and $x_2=1$ $x_1=2$ and $x_2=2$ so sequences is for this case $1, 1, 2, 2$ i am not sure that there is any clear relationship,let check again

let us add two more case

$n=14$ solutions are

$x_1=3$ and $x_2=2$ and $x_1=1$ and $x_2=3$ and $x_1=5$ and $x_2=1$,so there is three solution.now we get

$1,1,2,2,3$

let take $n=16$

we have following pairs

1)$x_1=2$ and $x_2=3$

2)$x_1=4$ and $x_2=2$

3) $x_1=6$ and $x_2=1$

so i think that for more and more even numbers,it increases by 1(number of solution) and
keeps it for the next even number too,like it for example increases number of solution by $1$ for $n=22$ for exmaple and also it keeps this amount for $n=24$

$\endgroup$
0
$\begingroup$

As stated, the generating function is: \begin{align} f(z) &= \frac{1}{1 - z^2} \cdot \frac{1}{1 - z^4} \\ &= \frac{1}{4 (1 - z^2)} + \frac{1}{4 (1 + z^2)} + \frac{1}{2 (1 - z^2)^2} \end{align} (this results from recognizing the generating function as a fraction in $z^2$, and splitting as such into partial fractions). Thus the expansion is: \begin{align} f(z) &= \frac{1}{4} \sum_{k \ge 0} \left( 1 + (-1)^k \right) z^{2 k} + \frac{1}{2} \sum_{k \ge 0} (-1)^k \binom{-2}{k} z^{2 k} \\ &= \frac{1}{4} \sum_{k \ge 0} \left( 1 + (-1)^k \right) z^{2 k} + \frac{1}{2} \sum_{k \ge 0} \binom{n + 1}{1} z^{2 k} \\ &= \frac{1}{4} \sum_{k \ge 0} \left( 1 + (-1)^k \right) z^{2 k} + \frac{1}{2} \sum_{k \ge 0} (k + 1) z^{2 k} \end{align} This gives the coefficients: $$ h_n = \begin{cases} 0 & \text{$n$ odd} \\ \left\lfloor \frac{n}{4} \right\rfloor + 1 & \text{$n$ even} \end{cases} $$ Thus $h_{2000} = 501$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.