Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Generating function"

m (Generating functions moved to Generating function: in keeping with general principle)
Line 1: Line 1:
 +
{{WotWAnnounce|week=Nov 15-21}}
 +
 
The idea behind '''generating functions''' is to create a [[power series]] whose [[coefficient]]s, <math>c_0, c_1, c_2, \ldots</math>, give the terms of a [[sequence]] which of interest. Therefore the power series (i.e. the generating function) is <math>c_0 + c_1 x + c_2 x^2 + \cdots </math> and the sequence is <math>c_0, c_1, c_2,\ldots</math>.
 
The idea behind '''generating functions''' is to create a [[power series]] whose [[coefficient]]s, <math>c_0, c_1, c_2, \ldots</math>, give the terms of a [[sequence]] which of interest. Therefore the power series (i.e. the generating function) is <math>c_0 + c_1 x + c_2 x^2 + \cdots </math> and the sequence is <math>c_0, c_1, c_2,\ldots</math>.
  
Line 5: Line 7:
 
If we let <math>A(k)={n \choose k}</math>, then we have <math>{n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+\cdots+</math><math>{n \choose n}x^n</math>.
 
If we let <math>A(k)={n \choose k}</math>, then we have <math>{n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+\cdots+</math><math>{n \choose n}x^n</math>.
  
−
This function can be described as the number of ways we can get <math>\displaystyle{k}</math> heads when flipping <math>n</math> different coins.
+
This function can be described as the number of ways we can get <math>{k}</math> heads when flipping <math>n</math> different coins.
  
 
The reason to go to such lengths is that our above polynomial is equal to <math>(1+x)^n</math> (which is clearly seen due to the [[Binomial Theorem]]). By using this equation, we can rapidly uncover identities such as <math>{n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n</math>(let <math>{x}=1</math>), also <math>{n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots</math>.
 
The reason to go to such lengths is that our above polynomial is equal to <math>(1+x)^n</math> (which is clearly seen due to the [[Binomial Theorem]]). By using this equation, we can rapidly uncover identities such as <math>{n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n</math>(let <math>{x}=1</math>), also <math>{n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots</math>.

Revision as of 12:14, 15 November 2007

This is an AoPSWiki Word of the Week for Nov 15-21

The idea behind generating functions is to create a power series whose coefficients, $c_0, c_1, c_2, \ldots$, give the terms of a sequence which of interest. Therefore the power series (i.e. the generating function) is $c_0 + c_1 x + c_2 x^2 + \cdots$ and the sequence is $c_0, c_1, c_2,\ldots$.

Simple Example

If we let $A(k)={n \choose k}$, then we have ${n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+\cdots+$${n \choose n}x^n$.

This function can be described as the number of ways we can get ${k}$ heads when flipping $n$ different coins.

The reason to go to such lengths is that our above polynomial is equal to $(1+x)^n$ (which is clearly seen due to the Binomial Theorem). By using this equation, we can rapidly uncover identities such as ${n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n$(let ${x}=1$), also ${n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Generating_function&oldid=19520"