简单数列
设：
\[h_0,h_1,h_2,h_3...,h_n,... \]表示一个数列，其中 \(h_n\) 叫做数列的一般项或通项
我们称 \(s_i= \sum_{k=0}^n \limits h_k\) 为 \(h\) 数列的部分和
这些部分和形成一个新的数列 \(s_0,s_1,..s_n,...\) ，其通项为 \(s_n\)
等差数列：
\[h_0,h_0+q,h_0+2q,...,h_0+nq,... \]通项为：
\[h_n=h_0+nq \]部分和为:
\[s_n=(n+1)h_0+ \frac{qn(n+1)}2 \]等比数列：
\[h_0,qh_0,q^2h_0,...,q^nh_0,... \]通项为：
\[h_n=q^nh_0 \]部分和为:
\[s_n=\begin{cases} {\frac {q^{n+1}-1}{q-1}h_0}\ \ \ \ \ \ \ \ (q\ !=1)\\ {(n+1)h_0}\ \ \ \ \ \ \ (q=1)\\ \end{cases} \]斐波那契数列：
1. 部分和为：
\[s_n=\sum_{i=0}^n f_i=f_{n+2}-1 \]考虑归纳证明：
\(n=0\) 时：
\[f_0=f_1-1 ⟺ 0=1-1 \]显然成立
若 \(s_n=f_{n+2}-1\)，有：
\[s_{n+1}=s_n+f_{n+1}=f_{n+1}+f_{n+2}-1=f_{n+3}-1 \]证毕
2. 通项公式：
\[f_n=\frac 1 {\sqrt 5}(\frac {1+\sqrt 5}{2})^n-\frac 1 {\sqrt 5}(\frac {1-\sqrt 5}{2})^n \]证明：
考虑如下形式的递推式
\[f_n-f_{n-1}-f_{n-2}=0 \]先忽略序列的初始值，寻找一种形式为 \(f_n=q^n\) 的解
\[q^n-q^{n-1}-q^{n-2}=0 \] \[q^{n-2}(q^2-q-1)=0 \]显然 \(q\) 不等于 \(1\) ，那么 \(q^2-q-1=0\)
解得 ：
\[q_1=\frac {1+\sqrt 5}2\ ,\ q_2=\frac {1-\sqrt 5}2 \]因此，\(f_n=(\frac {1+\sqrt 5}2)^n\) 或 \(f_n=(\frac {1-\sqrt 5}2)^n\) ，均满足递推关系
进而
\[f_n=c_0*(\frac {1+\sqrt 5}2)^n+c_1*(\frac {1-\sqrt 5}2)^n \]满足递推关系
因此，我们只需求解
\[\begin{cases} {c_0+c_1=a}\\ \\ {c_0*\frac {1+\sqrt 5}2+c_1*\frac {1-\sqrt 5}2=b}\\ \end{cases} \]即可求得以 \(a\)、\(b\) 为初值的斐波那契数列的通项
对于 \(a=1,b=1\) 的情况，解得：
\[f_n=\frac 1 {\sqrt 5}(\frac {1+\sqrt 5}{2})^n-\frac 1 {\sqrt 5}(\frac {1-\sqrt 5}{2})^n \]证毕
生成函数
绝大部分多项式科技都是在干同一件事 —— 通过代数手段优化卷积
设
\[h_0,h_1,h_2,h_3...,h_n,... \]是无穷数列，它的生成函数定义为无穷级数
\[g(x)=\sum_{i=0}^{\infty}\limits h_ix^i \]对于每一项都是 \(1\) 的序列，它的生成函数为：
\[g(x)=\sum_{i=0}^\infty \limits x^i \]由牛顿二项式定理:
\[(x+y)^n= \sum_{i=0}^\infty \limits \left(\begin{array}{c}a\\ k\end{array}\right)z^k \]其中，\(a\) 是实数，且
\[\left(\begin{array}{c}a\\ k\end{array}\right)=\frac {a(a-1)...(a-k+1)}{k!} \]令 \(z=x/y\)，则 \((x+y)^n=y^a(z+1)^a\)，有：
\[(1+z)^a=\sum_{i=0}^\infty \left(\begin{array}{c}a\\ k\end{array}\right)z^k \]由于：
\[\left(\begin{array}{c}-n\\ k\end{array}\right)=\frac {-n(-n-1)...(-n-k+1)}{k!} \] \[=(-1)^k\frac {n(n+1)...(n+k-1)}{k!} \] \[=(-1)^k\left(\begin{array}{c}n+k-1\\ k\end{array}\right) \]因此：
\[(1+z)^{-n}=\frac 1 {(1+z)^n}=\sum_{i=0}^\infty (-1)^i\left(\begin{array}{c}n+i-1\\ i\end{array}\right)z^k \]令 \(n=1\)，有：
\[\frac 1{1+z}=\sum_{i=0}^\infty (-1)^iz^i \]进而：
\[\frac 1{1-z}=\sum_{i=0}^\infty z^i \]因此
\[g(x)=\sum_{i=0}^\infty \limits x^i= \frac 1 {1-x} \]二项式系数\(\left(\begin{array}{c}m\\ 0\end{array}\right)\left(\begin{array}{c}m\\ 1\end{array}\right)...\left(\begin{array}{c}m\\ m\end{array}\right)\)的生成函数为：
\[g(x)=\sum_{i=0}^m\left(\begin{array}{c}m\\ i\end{array}\right)x^i=(1+x)^m \]进而，若 \(a\) 为实数，对于无穷数列：
\[\left(\begin{array}{c}a\\ 0\end{array}\right)\left(\begin{array}{c}a\\ 0\end{array}\right)...\left(\begin{array}{c}a\\ n\end{array}\right)... \]其生成函数为
\[g(x)=(1+x)^a=\sum_{i=0}^{\infty}\left(\begin{array}{c}a\\ i\end{array}\right)x^i \]设 \(k\) 为整数，设数列
\[h_0,h_1,h_2,h_3...,h_n,... \]\(h_n\) 表示 \(e_1+e_2+..+e_k=n\) 的正整数解个数
显然
\[h_n=\left(\begin{array}{c}n+k-1\\ k-1\end{array}\right) \]它的生成函数是
\[g(x)=\sum_{n=0}^{\infty}\left(\begin{array}{c}n+k-1\\ k-1\end{array}\right)x^n=\frac 1{(1-x)^k} \]结合前面的证明，有：
\[\frac 1{(1-x)^k}=\prod_{i=1}^{k}\frac{1}{1-x}=\prod_{i=1}^{k}\sum_{e_i=0}^\infty x^{e_i} \]将每一项取出，发现：
\[\prod_{i=1}^k x^{e_i}=x^n \]当且仅当：
\[\sum_{i=1}^k e_i=n \]因此 \(\frac 1{(1-x)^k}\) 每一项的系数即为 \(e_1+e_2+..+e_k=n\) 的正整数解个数
例题：
求装用苹果、香蕉、橘子和梨填充果篮的方案数 \(h_n\)，其中苹果数量必须是偶数，香蕉数量必须是 \(5\) 的倍数，橘子最多四个，梨最多一个
类似地，我们可以得到其生成函数：
\[g(x)=(\sum_{i=0}^\infty x^{2i})(\sum_{j=0}^\infty x^{5j})(\sum_{k=0}^4 x^{k})(1+x) \] \[=\frac 1{1-x^2}\frac{1}{1-x^5}\frac{1-x^5}{1-x}{}(1+x) \] \[=\frac 1{(1-x)^2}=\sum_{i=0}^\infty \left(\begin{array}{c}i+1\\ i\end{array}\right)x^i=(n+1)x^i \]因此，我们仅通过代数手段处理数列 \(h\) 的生成函数，得到了 \(h_i=i+1\)
生成函数解递推式
求 \(a_n=3*a_{n-1}\)，\(a_0=2\) 的通项：
设出其生成函数 \(G(x)=\sum_{i=0}^\infty \limits a_ix^i\)
有：
\[G(x)=a_0+\sum_{i=1}^\infty \limits 3a_{i-1}x*x^{i-1} \] \[=3xG(x)+2 \]整理得：
\[(1-3x)G(x)=2 \] \[G(x)=\frac 2 {1-3x}=\sum_{i=0}^\infty 2*(3x)^i \]因此
\[a_i=2*3^i \]求 \(a_n=8*a_{n-1}+10^{n-1}\)，\(a_0=1\) 的通项：
设出其生成函数 \(G(x)=\sum_{i=0}^\infty \limits a_ix^i\)
有：
\[G(x)=a_0+\sum_{i=1}^\infty \limits (8a_{i-1}+10^{i-1})x^{i} \] \[=a_0+\sum_{i=1}^\infty \limits 8a_{i-1}x*x^{i-1}+\sum_{i=1}^\infty \limits 10^{i-1}x^{i} \] \[=a_0+ 8xG(x)+\frac {x}{1-10x} \]整理得：
\[(8x-1)G(x)=-\frac {x}{1-10x}-a_0 \] \[(8x-1)G(x)=-\frac {1-9x}{1-10x} \] \[G(x)=\frac {1-9x}{(1-10x)(1-8x)} \] \[=\frac1 2(\frac 1{1-10x}+\frac 1 {1-8x}) \] \[=\frac 1 2(\sum_{i=0}^\infty 10^ix^i+\sum_{i=0}^\infty8^ix^i) \] \[=\sum_{i=0}^\infty \frac 1 2(10^i+8^i) x^i \]因此
\[a_i=\frac {10^i+8^1} 2 \]\[\]
关于裂项：部分分式展开法
普通生成函数：浅谈生成函数之OGF
指数生成函数：浅谈生成函数之EGF
[TJOI2015]概率论
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
printf("%.12lf",1.0*n*(n+1)/2/(2*n-1));
return 0;
}