How to find the generating function and the closed form for the generating form

6,163

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.

Share:
6,163

Related videos on Youtube

Mr.H123
Author by

Mr.H123

Updated on November 23, 2020

Comments

  • Mr.H123
    Mr.H123 almost 3 years

    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.

    • Mike Pierce
      Mike Pierce almost 9 years
      With the exception of the initial term of $0$, it's just $a_n = (-2)^n$.
    • André Nicolas
      André Nicolas almost 9 years
      Try $t/(1+2t)$.
    • Mr.H123
      Mr.H123 almost 9 years
      @mapierce271 : $$-2^2$$ isn't 4 but -4
    • Tacet
      Tacet almost 9 years
      @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.
    • Mr.H123
      Mr.H123 almost 9 years
      Sorry... I know, but it was just what my calculator gave me. Meant $$-2^0$$ It's not 1 but -1
    • Will Orrick
      Will Orrick almost 9 years
      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 ...
    • Will Orrick
      Will Orrick almost 9 years
      $-(2^2)=-4,$ and not as $(-2)^2=4.$ Some calculators with unary minus may be exceptions, but it pays to use explicit parentheses when unsure.
  • Mr.H123
    Mr.H123 almost 9 years
    So it's: $$A(x)=0+1x-2x^2+4x^3-8x^4+16x^5-32x^6+64x^7$$ ?
  • Mr.H123
    Mr.H123 almost 9 years
    ^^The generating form
  • Will Orrick
    Will Orrick almost 9 years
    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?
  • Mr.H123
    Mr.H123 almost 9 years
    No it's infinite
  • Mr.H123
    Mr.H123 almost 9 years
    Just tried to follow my teachers way of solving such sequences
  • Will Orrick
    Will Orrick almost 9 years
    Well, $A(x)$ should be in infinite sequence, not polynomial. I can't help much without knowing where you are getting stuck.
  • Mr.H123
    Mr.H123 almost 9 years
    The generating function is $$(-2)^n$$ but this doesn't give 0 or 1 (these are from the sequence)
  • Will Orrick
    Will Orrick almost 9 years
    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 ...
  • Will Orrick
    Will Orrick almost 9 years
    ... 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.