How to find the generating function and the closed form for the generating form
The generating function is $$ g(x)=0+1\cdot x2x^2+4x^38x^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.
Related videos on Youtube
Mr.H123
Updated on November 23, 2020Comments

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 yearsWith the exception of the initial term of $0$, it's just $a_n = (2)^n$.

André Nicolas almost 9 yearsTry $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 yearsSorry... I know, but it was just what my calculator gave me. Meant $$2^0$$ It's not 1 but 1

Will Orrick almost 9 yearsI 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 yearsSo it's: $$A(x)=0+1x2x^2+4x^38x^4+16x^532x^6+64x^7$$ ?

Mr.H123 almost 9 years^^The generating form

Will Orrick almost 9 yearsIn 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 yearsNo it's infinite

Mr.H123 almost 9 yearsJust tried to follow my teachers way of solving such sequences

Will Orrick almost 9 yearsWell, $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 yearsThe generating function is $$(2)^n$$ but this doesn't give 0 or 1 (these are from the sequence)

Will Orrick almost 9 yearsThe 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.