2
$\begingroup$

Find the generating functions of the sequences 2, 1, 2, 1, 2, 1, . . .

I get $\frac{1}{1+x} + \frac{1}{1-x} = \frac{2}{1-x^2}$

But the solution ends up with $\frac{2}{1-x^2} + \frac{x}{1-x^2} = \frac{2+x}{1-x^2}$. The solutions starts with $\sum_{n\ge 0} (2)x^{2n}+\sum_{n\ge 0} (1) x^{2n+1}$

I couldn't come up with anything like that. I feel like I'm confused with something.

$\endgroup$
  • $\begingroup$ you must have a typo.; $\dfrac2{1-x}+\dfrac x{1-x}=\dfrac{2+x}{1-x},$ not $\dfrac{2+x}{1-x^\color{red}2}$ $\endgroup$ – J. W. Tanner Dec 13 '19 at 1:21
  • 2
    $\begingroup$ The generating function of $1,1,1,1,...$ is $\frac{1}{1-x}$, while the generating function of $1,0,1,0,1,0,...$ is $\frac{1}{1-x^2}$. Then the generating function of $2,1,2,1,2,1,...$ should be $\frac{1}{1-x}+\frac{1}{1-x^2}$. $\endgroup$ – egorovik Dec 13 '19 at 1:22
  • 1
    $\begingroup$ Thanks. I fixed the typo. $\endgroup$ – user665125 Dec 13 '19 at 1:32
3
$\begingroup$

As $\frac{1}{1-x}$ is the generating series for $1,1,1,\dots$ and $\frac{1}{1-x}$ is the generating series for $1,-1,1,-1,\dots$, the series for which you are calculating the generating function for is $2,0,2,0,\dots$.

But we can get the result you want by noticing that $2,1,2,1,\dots$ is actually $\frac{3}{2},\frac{3}{2},\frac{3}{2},\dots$ plus $\frac{1}{2},-\frac{1}{2},\frac{1}{2},-\frac{1}{2},\dots$.

We know the first series has generating function $\frac{3/2}{1-x}$ and the second has generating function $\frac{1/2}{1+x}$. Thus, the function you are looking for is$$\frac{\frac{3}{2}}{1-x}+\frac{\frac{1}{2}}{1+x}=\frac{\frac{3}{2}(1+x)+\frac{1}{2}(1-x)}{(1-x)(1+x)}=\frac{2+x}{1-x^2}$$ which is the result you were given.

$\endgroup$
4
$\begingroup$

The sequence $2,1,2,1,2,1,...$ alternates between $2$ and $1$, being $2$ for even-numbered terms and $1$ for odd-numbered terms. The generating function is thus $$\sum\limits_{n \ge0}(2)x^{2n}+\sum\limits_{n\ge0}(1)x^{2n+1}=\sum\limits_{k\ge0}(1)x^k+\sum\limits_{k\ge0}(1)x^{2k}=\dfrac{1}{1-x}+\dfrac{1}{1-x^2}=\dfrac{2+x}{1-x^2}$$

$\endgroup$
2
$\begingroup$

As an alternative to the other answers, you can simply use a variant of one function, that being

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

If you consider that the $2$'s are even indexed (assuming in the sequence $\{a_n\}$ the first term is $a_0$) and the $1$'s are odd indexed, you have that

$$\frac{2}{1-x^2}$$

will generate the $2$'s and

$$\frac{x}{1-x^2}$$

will generate the $1$'s. This is because

$$\frac{1}{1-x^2}=1+x^2+x^4+...$$

and so

$$\frac{x}{1-x^2}=x(1+x^2+x^4+...)=x+x^3+x^5+...$$

Thus, you sequence will be generated by

$$f(x)=\frac{2+x}{1-x^2}$$

$\endgroup$
0
$\begingroup$

And if you want to generate $(a_i)_{i=1}^m$ repeatedly, the i-th term is generated by $a_ix^i$, and for this to repeat every $m$ this needs $\dfrac{a_ix^i}{1-x^m} $ so the final result is $\sum_{i=1}^m\dfrac{a_ix^i}{1-x^m} $.

In your case, with $(1, 2)$ repeated, this is $\dfrac{x}{1-x^2}+\dfrac{2x^2}{1-x^2} =\dfrac{x+2x^2}{1-x^2} $.

This starts the first term at $x^1$. To start it at the constant term, just reduce the exponents of the $x^i$ by one giving $\sum_{i=1}^m\dfrac{a_ix^{i-1}}{1-x^m} $, so this gives, in this case $\dfrac{1}{1-x^2}+\dfrac{2x}{1-x^2} =\dfrac{1+2x}{1-x^2} $.

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