以下等式或者不等式均可以用数学归纳法予以证明! 1 + 3 + 5 + ... + (2n - 1) = n^2 1*2 + 2*3 + 3*4 + ... + n*(n + 1) = n*(n + 1)*(n + 2)  3 1*1! + 2*2! + 3*3! + ... + n*n! = (n + 1)! - 1 1^2 + 2^2 + 3^2 + ... + n^2 = n*(n + 1)*(2n + 1)  6 1^2 - 2^2 + 3^2 .. + (-1)^n * n^2 = (-1)^(n + 1) * n * (n + 1)  2 2^2 + 4^2 + ... + (2n)^2 = 2n*(n+1)*(2n+1)  3 12! + 23! + ... + n(n+1)! = 1 - 1(n+1)! 2^(n + 1)  1 + (n + 1)2^n 1^3 + 2^3 + 3^3 + ... + n^3 = (n*(n + 1)  2)^2 1(2*4)+1*3(2*4*6)+1*3*5(2*4*6*8)+...+(1*3*5*...*(2n-1))(2*4*6*...*(2n+2)) = 12 - (1*3*5*...*(2n+1)) (2*4*6*...*(2n+2)) 1(2^2-1) + 1(3^2-1) + .. + 1  ((n+1)^2 - 1) = 34 - 1(2*(n+1)) - 1(2*(n+2)) 12n = 1*3*5*...*(2n-1)  (2*4*6*...*2n) = 1  sqrt(n+1) n=1,2... 2^n = n^2 , n=4, 5.. 2^n = 2n + 1, n=3,4.. r^0 + r^1 + ... + r^n  1  (1 - r), n=0, 0r1 1*r^1 + 2*r^2 + ... + n*r^n  r  (1-r)^2, n=1, 0r1 12^1 + 22^2 + 32^3 + ... + n 2^n  2, n=1 (a(1)*a(2)*...*a(2^n))^(12^n) = (a(1) + a(2) + ... + a(2^n))  2^n, n = 1, 2, ... a(i)是正数 注:用来标记下标 cos(x) + cos(2x) + ... + cos(nx) = cos((x2)*(n+1))*sin(nx2)  sin(x2), 其中sin(x2) != 0 1*sin(x) + 2*sin(2x) + ... + n*sin(nx) = sin((n+1)*x)  (4*sin(x2)^2) - (n+1)cos((2n + 1)2 * x)  (2 * sin(x2)) 其中sin(x2) != 0 5^n - 1能被4整除 7^n - 1能被6整除 11^n - 6能被5整除 6*7^n - 2*3^n能被4整除 3^n + 7^n - 2能被8整除 n条直线能将平面最多划分为(n^2 + n + 2)  2个区域 定义h(k) = 1 + 12 + 13 + ... + 1k 则 1 + n2 =h(2^n) = 1 + n h(1) + h(2) + ... + h(n) = (n + 1) * h(n) - n 1*h(1) + 2*h(2) + ... + n*h(n) = n*(n + 1)  2 * h(n + 1) - n * (n + 1)  4 欧拉函数的定义:e(k)=([1,n-1]中与n互质的整数个数).因为任意正整数都可以唯一表示成如下形式: k=p1^a1*p2^a2*...*pi^ai;(即分解质因数形式) 可以推出:e(k)=(p1-1)(p2-1)...(pi-1)*(p1^(a1-1))(p2^(a2-1))...(pi^(ai-1)) ???? =k*(p1-1)(p2-1)...(pi-1)(p1*p2*...pi); ???? =k*(1-1p1)*(1-1p2)....(1-1pk) 在程序中利用欧拉函数如下性质,可以快速求出欧拉函数的值(a为n的质因素) 若(n%a==0 && (na)%a==0) 则有:e(n)=e(na)*a; 若(n%a==0 && (na)%a!=0) 则有:e(n)=e(na)*(a-1); 若n2, 欧拉函数e(n)必定是偶数 若gcd(a,b) = 1,则有e(a * b) = e(a) * e(b) 若一个数n分解成p1^a1 * p2^a2 * ... * pn^an,那么 e(n) = p1^(a1 - 1) * (p1 - 1) * ... * pn^(an - 1) * (pn - 1) 若n1,不大于n且与n互素的所有正整数的和是12 * n * e(n) 因子和: 若 k=p1^a1*p2^a2...*pi^ai?? f(k) = (p1^0+...+p1^a1)*(p2^0+...+p2^a2)*...*(pi^0 + ... + pi^ai) 没有一个平方数是以2,3,7,8结尾的 max{a, b, c} - min{a, b, c} = (|a - b| + |b - c| + |a - c|)  2 ac % m = bc % m 可以得到 a % m = b % m m = m  gcd(m, c) 如果a % mi = b % mi (i=1,2..,n) 并且 l = lcm(m1, m2, ..., mn) 则可以得到 a % l = b % l e ler 定理 若gcd(a,m)==1, 则a^(phi(m)) % m = 1 % m fermat小定理 p为素数,对任意的a有 a^p % p = a % p p为素数 ,对任意的a(ap), a^(p-1) % p = 1 % p p为素数 , 对任意的a,若gcd(p,a)==1, a^(p-1) % p = 1 % p 一个奇数a的平方减1都是8的倍数 任意4个连续整数的乘积再加上1 一定是完全平方数 当a是整数时,a(a-1)(2a-1)是6的倍数 当a是奇数时,?? a(a^2 - 1)是24的倍数 n次代数方程 x^n + a1 * x^(n-1) + ... + an-1*x + an = 0 的系数都是a1, a2, ... , an都是整数. 如果它有有理数的根,证明这个根一定是整数,而且这个数一定是an的因子.如果不是整数,就一定是无理数. 设a,b都是正整数,ab而gcd(a,b) = 1 ,如果存在一个素数p,它能够整除b,但是不能够整除10,则ab一定不能够化成有限小数.如果b=2^a * 5^b,其中a,b都是非负整数,则ab能化成有限小数. 设0ab, 且gcd(a,b) = 1, 如果ab能表示成纯循环小数,则我们有gcd(b, 10) = 1. 设0ab, 且gcd(a,b) = 1, 令h是一个最小的正整数,使得10^h 与1 关于b同余,那么ab可以表示成纯循环小数 0.d1d2d3...dh. 设b是一个正整数且gcd(10, b) = 1,令h是一个最小的正整数,能使得10^h 与1 关于b同余,则h能够整除e ler(b) 设a, b, b1都是正整数,a  b, gcd(a, b) = 1, b1  1, gcd(b1, 10) = 1.b = 2^c * 5^d * b1, 其中c, d都是非负整数,且不同时为0,令h是一个最小的正整数,使得 10^h 与1 关于b1同余, 则当c=d时,我们有ab = 0.a1a2...aca (c+1)...a (c + h) ,而当c  d时,我们有ab = 0.a1a2...ada (d+1)...a (d + h) 设0.a1a2...an...不能换成有限小数,也不能化成循环小数,则它不能化成分数. 设p是一个素数,m是一个正整数且m=na+b其中a是一个非负整数而b是一个不大于n-1的非负整数.令 a=p^m, 当b=0的时候,a的开n次方是一个整数,当1= b = n - 1时,a的开n次方不能表示为分数. 设p是一个素数,m是一个正整数且m=na+b其中a是一个非负整数而b是一个不大于n-1的非负整数.令 a=p^m, 当b=0的时候,a的开n次方是一个整数,当1= b = n - 1时,a的开n次方=b+c, 其中b是一个正整数而c是一个无限小数但不是循环小数. 设a是一个正整数, 当a的开n次方=b+c中b是一个正整数而0c1时,则a的开n次方不能表示成为分数,并且这时c是一个无限小数但不是循环小数. (4b^3 + 3b)  (4b^2 + 1) = b + 1  (2b + 12b) = 根号b平方+1 = b + 1  (2b + 1(2b + 1  2b)) = (8b^4 + 8b^2 + 1)  (8b^3 + 4b) b + 1(2b + 1(2b + 1(2b + 12b = 根号b平方+1 (16b^5 + 20b^3 + 5b)  (16b^4 + 12b^2 + 1) = 根号b平方+1 = (8b^4 + 8b^2 + 1)  (8b^3 + 4b) 8*8棋盘2牌的完美覆盖数目为=2^4 * 901^2 一张m行n列棋盘有一个b-牌的完美覆盖,当且仅当b是m的一个因子或者b是n的一个因子 n阶幻方的幻和为 n*(n^2+1)  2?? n阶幻方体的幻和为(n^4+n)  2 鸽巢原理: 如果n+1个物体被放进n个盒子,那么至少有一个盒子包含两个或者更多的物体 鸽巢原理加强形式: 令q1,q2.,qn为正整数.如果将 q1+q2+...+qn-n+1 个物体放入n个盒子内,那么,至少第一个盒子至少含有q1个物体,或者第二个 盒子至少含有q2个物体.. ,或者第n个盒子至少含有qn个物体 给定m个整数a1,a2..,am,存在整数p和q,0=pq=m,使得a(p+1)+a(p+2)+...+a(m)能够被m整除.通俗的说,就是在序列a1,a2..,am中存在连续 个a,使得这些a的和能被m整除 由n^2+1个实数构成的序列a1,a2..,a(n^2+1)或者含有长度为n+1的递增子序列,或者含有长度为n+1的递减子序列 ramsey定理:在6个(或更多的)人中,或者有3个人,他们中的每两个人都互相认识;或者有3个人,他们中的每两个人都彼此不认识 n个元素的集合的循环r-排列的个数由 a(n,r)r=n!(r * (n-r)!)给出.特别地,n个元素的循环排列的个数是(n-1)! 多重集排列: 令s是一个多重集,有k个不同类型的元素,各元素的重数分别为n1,n2..,nk.设s的大小为n=n1+n2+...+nk.则s的排列数等于n!(n1!*n2!*...*nk!) 多重集的组合: 令s为具有k中类型元素的一个多重集,每种元素均具有无限的重复数.则s的r-组合的个数等于 c(r+k-1,r) 如果排列p1p2...pn有 逆序列b1,b2..,bn,且k=b1+b2+...+bn为逆序数,那么p1p2...pn可以通过k次连续交换得到12...n 利用反射gray码生成相邻元组1的个数相差1的所有组合 生成{1,2..,n}的字典序r-组合的算法: 从r-组合a1a2...ar=12..r开始 当a1a2...ar不等于(n-r+1)(n-r+2)...n时,做: i)确定最大的整数k,是的ak + 1=n且ak + 1不等于a1,a2..ar ii)用r-组合?? a1...a(k-1)(ak + 1)(ak+2)...(ak + r - k + 1)替换 a1a2...ar c(n,k)=c(n-1,k)+c(n-1,k-1) 1=k=n-1 k * c(n,k) = n * c(n-1, k-1) c(n,0)+c(n,1)+...+c(n,n) = 2^n??? c(n,0)+c(n,2)+... = 2^(n-1) c(n,1)+c(n,3)+...=2^(n-1) 1*c(n,1)+2*c(n,2)+...+n*c(n,n)=n*2^(n-1) (n=1) 通过对等式 (1+x)^n=sigma(c(n,k)*x^k) k: 0-n 两边就微分,可以得到 sigma(k^p * c(n,k)) k: 1-n的和 sigma(c(n,k)^2) = c(2n,n) k: 1-n c(r,0)+c(r+1,1)+...+c(r+k,k) = c(r+k+1,k) c(0,k)+c(1,k)+...+c(n-1,k)+c(n,k)=c(n+1,k+1) dilworth定理: 令(x,=)是一个有限偏序集,并令m是反链的最大大小.则x可以被划分成m个但不能再少的链 同理, 若r是链的最大大小,那么x可以被划分成r个但不能再少的反链. 卷积定理: 对任意两个长度为n的向量a和b,其中n是2的幂, a,b的卷积等于 (dft2n)-1(dft2n(a) . dft2n(b)) 其中向量a和b是用0扩充使其长度达到2n,"."表示2个2n个元素组成的向量的点乘  素数  最小质因子为11  最小质因子为 中线定理(papp s定理)是指三角形abc内bm=mc,则ab^2+ac^2=2*(am^2+bm^2) 证明: ac^2=ah^2+hc^2? ab^2=ah^2+bh^2=ah^2+(hc+2mh)^2=ah^2+hc^2+4mh*hc+4mh^2 左边=ab^2+ac^2=2*ah^2+2ch^2+4mh*ch+4mh^2 右边=2*(am^2+bm^2)=2*(ah^2+mh^2+(ch+mh)^2)=2*(ah^2+mh^2+ch^2+2ch*mh+mh^2) 得证 (1)定理:设x0,x1,x2..是无穷实数列,xj0,j=1,那么, ? (i)对任意的整数 n= 1, r=1有 ?? x0..,xn-1,xn..,xn+r = x0..,xn-1,xn..,xn+r ?? =??? x0..,xn-1,xn+1xn+1..,xn+r. ? 特别地有 ?? x0..,xn-1,xn,xn+1 = x0..,xn-1,xn+1xn+1 ?注:用该定理可以求连分数的值 (2)对于连分数数数列 x0..xn 有递推关系: ? pn = xnpn-1+pn-2; ? qn = xnqn-1+qn-2; ? 定义: p-2 = 0; p-1 = 1; q-2 = 1; q-1 = 0; ? 所以:?? p0 = x0; q0 = 1; p1 = x1x0+1; q1 = x1; ? 特别地:当 xi=1 时, {pn}, {qn}为fbi数列 (3)对于连分数数数列 x0..xn ???? 当n= 1时,我们有pkqk-1 = pk-1qk = (-1)^k ???? 当n=2时, 我们有pkqk-2 = pk-2qk = (-1)^(k - 1) * xk (4) 所有有理数都可以表示成有限连分数 (5)pell方程: x^2+ny^2=+-1的解法: ? 若n是平方数,则无解, 否则: ? 先求出sqrt(n)的连分数序列x0,x1..xn 其中xn = 2*x0; ? 对于 x^2+ny^2=-1 ? 若n为奇数,则 x=pn-1, y=qn-1; n为偶数时无解 ? 对于 x^2+ny^2=1 ? 若n为偶数,则 x=pn-1, y=qn-1; n为奇数时x=p2n-1, y=q2n-1 ?