下载文档原格式
![[数学]组合数学第7章[递推关系与生成函数]](https://img.taocdn.com/s1/m/da793af0c1c708a1284a4443.png)
生成函数及其应用
生成函数是一种常见的数学工具，它可以将一个数列或者函数序列表示成一个函数的形式。
生成函数不仅在组合数学中有广泛的应用，还被广泛应用于物理、统计学、计算机科学等领域。
生成函数的基本定义是将一个数列或函数序列 $a_0, a_1, a_2, cdots$ 表示成一个形式为 $f(x)$ 的函数。
通常情况下，生成函数
可以写成幂级数的形式，即 $f(x) = sum_{n=0}^{infty} a_n x^n$。
其中，$x$ 是一个实数或者复数。
生成函数的应用非常广泛，其中最重要的应用之一是求解组合计数问题。
在组合数学中，通常需要求解某种组合对象的计数问题，例如排列、组合、集合等问题。
而生成函数可以帮助我们将这些计数问题转化为函数求值问题，进而通过函数的性质来求解原问题。
除了在组合计数问题中的应用，生成函数还被广泛应用于求解递推关系式、求解微分方程、分析算法复杂度等领域。
在物理学中，生成函数也被用来描述统计物理中的一些问题，例如统计热力学、量子场论等。
总之，生成函数是一种非常重要的数学工具，它在多个领域都有着广泛的应用。
掌握生成函数的基本理论和应用，对于深入理解组合数学、物理、计算机科学等领域的问题都有着重要的帮助。
- 1 -。
总结：⽣成函数（斐波那契通项公式推导）⽣成函数总结前⾔形式幂级数先讲讲什么是幂级数叭幂级数是指级数的每⼀项均为与级数项序号n相对应的以常数倍的 (x−a) 的n(n∈N) 次⽅。
⽐如A(x)=∑i≥0a i(x−x0)i它与多项式不同的⼀点在于多项式只有有限项的系数是⾮零的。
接着讲形式幂级数其意思就是：对于我们⽣成的这个多项式来说，其中的变量x只是作为⼀个符号⽽已，只是⼀个形式，它的取值并不重要，我们关⼼的只是它所携带的信息⽽已。
好惨⼀变量……就⽐如在最简单的⽣成函数⽅案统计问题中，其指数就是我们要求的⽅案，⽽其系数就是答案。
后⾯讲⽣成函数的时候会细讲。
⽣成函数⽣成函数可以分为很多种，但是⽤的最⼴泛的还是普通⽣成函数和指数⽣成函数。
普通⽣成函数Ordinary Generating Function,OGF：普通⽣成函数。
定义为形式幂级数：F(x)=∑n≥0a n x n封闭形式每次计算都要写⼀长串的多项式或者写⼀个 ∑，太⿇烦了，有没有更好的⽅法？⾃然是有的，我们发现：对于序列<1,1,1,…>的普通⽣成函数F(x)=∑n≥0x n，有F(x)⋅x+1=F(x)解得F(x)=11−x，所以我们可以⽤这个来代替原来琐碎的 ∑并简化运算。
真是天⾐⽆缝⼜⼗分扯淡这种⽅法⽤的⾮常多，尤其是在求通项公式的时候，⽐如求斐波那契和卡特兰数的通项公式时就会⽤到。
⼆项式定理但是我们将⼀个多项式变成封闭形式之后就⽆法得到第n项的系数了啊。
但是没有关系，我们可以⽤⼆项式定理将其展开。
Generalized Binomial Theorem:⼴义⼆项式定理：(x+y)α=∞∑k=0αk xα−k y k ()() Processing math: 100%其中αk为⼴义⼆项式系数（其实就是实数域下的组合数）αk=αk_k !=α(α−1)…(α−k +1)k !,α∈R,k ∈Nαk_ 表⽰ α 的 k 次下降幂，即 α(α−1)…(α−k +1)。
求数列通项公式的几种基本方法一、递推法递推法是一种常用的求解数列通项公式的方法。
它是基于数列中的前一项或前几项与后一项或后几项之间的关系来推导数列的通项公式。
通过观察数列中的规律，我们可以写出数列中相邻两项之间的递推关系式，并利用该关系式递推得到数列的通项公式。
举例说明，假设要求解数列的通项公式：1,3,5,7,9,...通过观察数列可以发现，每一项都比前一项大2，可以推测数列的递推关系式为an = an-1 + 2、其中an表示数列中的第n项。
进一步，假设第一项为a1，则有a2 = a1 + 2，a3 = a2 + 2，依此类推。
通过这种方式，可以逐步得到数列中的每一项。
在本例中，由于数列的首项为1，所以数列的通项公式为an = 2n-1二、代数法代数法是另一种常用的求解数列通项公式的方法。
它通过假设数列的通项公式为一些未知数表达式，然后通过已知条件求解未知数的值，从而得到数列的通项公式。
举例说明，假设要求解数列的通项公式：1,4,9,16,25,...通过观察数列可以发现，每一项都是一些整数的平方。
假设数列的通项公式为an = n^2，其中n表示数列中的第n项。
我们可以通过验证前几项来确定这个假设是否成立。
在本例中，当n=1时，a1 = 1^2 = 1，当n=2时，a2 = 2^2 = 4，通过验证可知假设成立，因此数列的通项公式为an = n^2三、解方程法解方程法也是一种常用的求解数列通项公式的方法。
它通过设立数列中的一些项之间的方程，然后求解这个方程，从而得到数列的通项公式。
举例说明，假设要求解数列的通项公式：2,5,10,17,26,...通过观察数列可以发现，每一项都比前一项大3、5、7、9，可以推测数列的递推关系式为an = an-1 + 1 + (2n-1)。
其中an表示数列中的第n项。
进一步，假设第一项为a1，则有a2 = a1 + 1 + 1，a3 = a2 +1 + 3，依此类推。
第七章递推关系与生成组合3.证明：（1）必要性：fn是偶数n可被3整除.用第二数学归纳法：当k=3时，f3=f2+f1=2是偶数，n=3可被3整除。
假设n≤k时，若fn是偶数n可被3整除。
当n>k时，若fn是偶数，则fn=fn-1+fn-2=2fn-2+fn-3,可得fn-3=fn - 2fn-2.因为fn是偶数，2fn-2是偶数，所以fn-3是偶数。
因为n-3≤k,由归纳法假设，n-3可被3整除，所以n可被3整除。
（2）充分性：n可被3整除fn是偶数。
用第二归纳法：当k=3时，k可被3整除，f3=f2+f1=2是偶数。
假设n≤k时，若n可被3整除，fn是偶数。
当n>k时，fn=2fn-2+fn-3.由归纳法假设fn-3是偶数，所以fn是偶数。
所以fn是偶数的充要条件是n可被3整除。
4.证明：设fn是斐波那契序列，则有fn =fn-1+fn-2=2fn-2+fn-3=3fn-3+2fn-4=5fn-4+3fn-5且f0=0,f1=1,f2=1,f3=2,f4=3.所以斐波那契序列是递推关系an=5an-4+3an-5(n≥5)的解，其中，a0=0,a1=1,a2=1,a3=2,a4=3.（1）必要性：fn可被5整除n可被5整除.用第二数学归纳法：当k=5时，f5=5f1+3f0=5可被5整除，n=5可被5整除。
假设n≤k时，若fn可被5整除n可被5整除。
当n>k时，若fn可被5整除，则fn=5fn-4+3fn-5,可得3fn-5=fn-5fn-4.因为fn可被5整除，5fn-4可被5整除，所以3fn-5可被5整除, 所以fn-5可被5整除。
因为n-5≤k,由归纳法假设，n-5可被5整除，所以n可被5整除。
（2）充分性：n可被5整除fn可被5整除。
用第二归纳法：当k=5时，k可被5整除，f5=5f1+3f0=5可被5整除。
假设n≤k时，若n可被5整除，fn可被5整除。
当n>k时，fn=5fn-4+3fn-5.由归纳法假设fn-5可被5整除，所以fn可被5整除。
