2
$\begingroup$

I'm trying to find the generating function and the closed form for the generating form for this sequence:

$0,1,-2,4,-8,16,-32,64...$

I've tried the following:

I think it's an index shift so that's why the generating function is: $a_n= $?

What about the closed form? Can you please tell how I solve this, and not only the result.

$\endgroup$
7
  • 1
    $\begingroup$ With the exception of the initial term of $0$, it's just $a_n = (-2)^n$. $\endgroup$
    – Mike Pierce
    Commented Nov 22, 2014 at 20:07
  • 1
    $\begingroup$ Try $t/(1+2t)$. $\endgroup$
    – André Nicolas
    Commented Nov 22, 2014 at 20:13
  • $\begingroup$ @mapierce271 : $$-2^2$$ isn't 4 but -4 $\endgroup$
    – Mr.H123
    Commented Nov 22, 2014 at 23:09
  • $\begingroup$ @Mr.H123 You have absolutely no basic informations about math. Please, start from scratch. It is 4. $$(-2)^2 = (-2)\cdot(-2) = 4$$ And please don't understand it as an attempt to insult. I just don't know how to help you, as long as you do not have such informations. I worry about you. Over time, the more problems will arrive. $\endgroup$
    – Tacet
    Commented Nov 22, 2014 at 23:59
  • 3
    $\begingroup$ I think I agree with Tacet that these are the sorts of arithmetic operations that you need to be able to handle correctly with ease before you can tackle a topic like generating functions. Try not using a calculator to compute the powers of $-2.$ A rule you should know is that $a^0=1$ for any $a\ne0.$ (The expression $0^0$ is undefined.) You should also know that whole number exponents mean repeated multiplication. So $(-2)^1=-2,$ $(-2)^2=(-2)(-2)=4,$ $(-2)^3=(-2)(-2)(-2)=-8,$ and so on. You should be careful about parentheses. Expressions like $-2^2$ are interpreted as ... $\endgroup$
    – Will Orrick
    Commented Nov 23, 2014 at 21:56

1 Answer 1

Reset to default
3
$\begingroup$

The generating function is $$ g(x)=0+1\cdot x-2x^2+4x^3-8x^4+16x^5-\ldots. $$ Observe that each coefficient starting with the coefficient of $x^2$ is $-2$ times the coefficient of the previous term. This suggests the idea of multiplying $g(x)$ by $-2x$ and subtracting the result from $g(x).$ If you do this, you will find that all terms cancel but one. So you have $g(x)-(-2xg(x))$ equals the leftover term. You should then be able to solve for $g(x)$ algebraically.

$\endgroup$
9
  • $\begingroup$ So it's: $$A(x)=0+1x-2x^2+4x^3-8x^4+16x^5-32x^6+64x^7$$ ? $\endgroup$
    – Mr.H123
    Commented Nov 22, 2014 at 22:51
  • $\begingroup$ ^^The generating form $\endgroup$
    – Mr.H123
    Commented Nov 22, 2014 at 22:55
  • $\begingroup$ In your post, you wrote the sequence as $$0,\ 1,\ -2,\ 4,\ -8,\ 16,\ -32,\ 64\ldots,$$ which led me to believe that the sequence was infinite. Why do you terminate the sequence with the $x^7$ term? Is it actually a finite sequence? $\endgroup$
    – Will Orrick
    Commented Nov 23, 2014 at 3:36
  • 2
    $\begingroup$ The expression $(-2)^n$ is not the generating function. It is a (not quite correct) formula for the terms in the sequence. A generating function for the sequence $a_0,$ $a_1,$ $a_2,$ $a_3,$ $\ldots$ is $a_0+a_1x+a_2x^2+a_3x^3+\ldots.$ Such an expression with an indeterminate $x$ is known as a formal power series. Your sequence is $a_0=0,$ $a_1=1,$ $a_2=-2,$ $a_3=4,$ $\ldots.$ You need to multiply these numbers by appropriate powers of $x$ and sum the resulting terms to get a generating function. The formula you give does have the problem you mention: it doesn't produce the initial ... $\endgroup$
    – Will Orrick
    Commented Nov 24, 2014 at 2:21
  • 2
    $\begingroup$ ... term, $0.$ Another problem is that the index is off by $1.$ So $a_2=-2$ but $(-2)^1=-2$. Similarly $a_3=4$ but $(-2)^2=4.$ So $a_n=(-2)^n$ is not a true statement. To get a correct formula, you need to modify the exponent slightly. With this correction, the formula will be correct for all elements of the sequence except $a_0.$ (It will even work for $a_1$ since $(-2)^0=1.$) You can't really write a simple formula that works also for $a_0,$ so I would just make that a special case. This exception at $a_0$ is easier to deal with in the generating function context. $\endgroup$
    – Will Orrick
    Commented Nov 24, 2014 at 2:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .