# 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

Author by

### Mr.H123

Updated on November 23, 2020

• 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 almost 9 years
With the exception of the initial term of $0$, it's just $a_n = (-2)^n$.
• André Nicolas almost 9 years
Try $t/(1+2t)$.
• Mr.H123 almost 9 years
@mapierce271 : $$-2^2$$ isn't 4 but -4
• 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 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 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 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 almost 9 years
So it's: $$A(x)=0+1x-2x^2+4x^3-8x^4+16x^5-32x^6+64x^7$$ ?
• Mr.H123 almost 9 years
^^The generating form
• 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 almost 9 years
No it's infinite
• Mr.H123 almost 9 years
Just tried to follow my teachers way of solving such sequences
• 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 almost 9 years
The generating function is $$(-2)^n$$ but this doesn't give 0 or 1 (these are from the sequence)
• 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 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.