1
$\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$
  • $\begingroup$ With the exception of the initial term of $0$, it's just $a_n = (-2)^n$. $\endgroup$ – Mike Pierce Nov 22 '14 at 20:07
  • 1
    $\begingroup$ Try $t/(1+2t)$. $\endgroup$ – André Nicolas Nov 22 '14 at 20:13
  • $\begingroup$ @mapierce271 : $$-2^2$$ isn't 4 but -4 $\endgroup$ – Mr.H123 Nov 22 '14 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 Nov 22 '14 at 23:59
  • 2
    $\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 Nov 23 '14 at 21:56
1
$\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$
  • $\begingroup$ So it's: $$A(x)=0+1x-2x^2+4x^3-8x^4+16x^5-32x^6+64x^7$$ ? $\endgroup$ – Mr.H123 Nov 22 '14 at 22:51
  • $\begingroup$ ^^The generating form $\endgroup$ – Mr.H123 Nov 22 '14 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 Nov 23 '14 at 3:36
  • 1
    $\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 Nov 24 '14 at 2:21
  • 1
    $\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 Nov 24 '14 at 2:30

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.