1
$\begingroup$

I am trying to compute the generating function for the number sequence given by $a_n = (-1)^n$. I know that the solution is $A(x) = \frac{1}{1+x}$ but when I try to solve it using the procedure of finding the formal power series and then computing the generating function I don't even know where to begin. I hope someone can help.

$\endgroup$
  • $\begingroup$ If you know the standard geometric series, then it's pretty much obvious that $$\sum_n (-1)^n x^n = \sum_n (-x)^n = \frac{1}{1-(-x)} = \frac{1}{1+x}$$ $\endgroup$ – Crostul Jun 16 '16 at 12:20
1
$\begingroup$

The main point is to write a recurrence for the sequence $a_n$: $$ a_{n+1}=-a_n, \qquad a_0=1 $$ The shift from $n$ to $n+1$ is reflected in $A(x)$ as multiplication by $x$.

Therefore, if $A(x)= \sum a_n x^n$, then $xA(x)=1-A(x)$. Now solve for $A(x)$.

$\endgroup$
1
$\begingroup$

Suppose the generating function is $f(x)$. Then you have $$f(x)=1-x+x^2-x^3+\dots$$

Hence $$xf(x)=x-x^2+x^3-\dots$$

Adding these two we get $f(x)+xf(x)=1$, so $$f(x)=\frac{1}{1+x}$$

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