数列求和公式汇总

常见公式

1+2+3+…+n=n(n+1)/2

LL getSum(LL n) {//等差数列求和公式 return (n+1)*n/2;//注意(n+1)/2*n这样不对 }

q^1+q^2+q^3+…+q^n=q*(q^n-1)/(q-1)

LL power(int a,int b){ LL ans=1,base=a; while(b>0){ if(b&1) //n%2==1 ans=ans*base; base=base*base; b>>=1;// b/=2 } return ans; } LL getSum(LL q,LL n) {//等比数列求和公式 return q*(power(q,n)-1)/(q-1); }

1²+2²+3²…+n²=n(n+1)(2n+1)/6

推导过程

利用立方差公式 n^3-(n-1)^3=1*[n^2+(n-1)^2+n(n-1)] =n^2+(n-1)^2+n^2-n =2*n^2+(n-1)^2-n 2^3-1^3=2*2^2+1^2-2 3^3-2^3=2*3^2+2^2-3 4^3-3^3=2*4^2+3^2-4 . n^3-(n-1)^3=2*n^2+(n-1)^2-n 各等式全相加 n^3-1^3=2*(2^2+3^2+…+n^2)+[1^2+2^2+…+(n-1)^2]-(2+3+4+…+n) n^3-1=2*(1^2+2^2+3^2+…+n^2)-2+[1^2+2^2+…+(n-1)^2+n^2]-n^2-(2+3+4+…+n) n^3-1=3*(1^2+2^2+3^2+…+n^2)-2-n^2-(1+2+3+…+n)+1 n^3-1=3(1^2+2^2+…+n^2)-1-n^2-n(n+1)/2 3(1^2+2^2+…+n^2)=n^3+n^2+n(n+1)/2=(n/2)(2n^2+2n+n+1) =(n/2)(n+1)(2n+1) 1^2+2^2+3^2+…+n^2=n(n+1)(2n+1)/6

编码实现

LL getSum(LL n) { return (n+1)*n*(2*n+1)/2; }

1³+2³+3³+…n³=n²(n+1)²/4=[n(n+1)/2]²

LL getSum(LL n) { return n*n*(n+1)*(n+1)/4; }

1^4+2^4+3^4+…+n^4=n(n+1)(2n+1)(3n^2+3n-1)/30

LL getSum(LL n) { return n*(n+1)*(2*n+1)*(3*n*n+3*n-1)/30; }

1*2+2*3+3*4+4*5+…+n(n+1)=n(n+1)(n+2)/3

LL getSum(LL n) { return n*(n+1)*(n+2)/3; }

对公式有特殊的取模处理时

例如对公式1^4+2^4+3^4+…+n^4=n(n+1)(2n+1)(3n^2+3n-1)/30。如果有题目要求对其取模，如果对于公式算完再取模，数很大的情况，会溢出，我们就要对每一步先取模运算，防止溢出，我们知道对于出现除法的取模运算不能像加减乘一样直接对每一部分直接取模，要用逆元取模。 这里就是对上式的一个取模实验。这里用的是费马小定理。

#include <cstdio> #include <cmath> using namespace std; typedef long long LL; typedef long long LL; LL pow_mod(LL a,LL b,LL m){ LL ans=1,base=a; while(b>0){ if(b&1) //n%2==1 ans=ans*base%m; base=base*base%m; b>>=1;// b/=2 } return ans; } LL getSum(LL n) { return n*(n+1)%mod*(2*n+1)%mod*(3*(n*n%mod)+3*n-1)%mod*pow_mod(30,mod-2,mod)%mod; } int main() { printf("%lld",getSum(2,1e9+7)); return 0; }

斐波那契数列求和公式

Sn=A(n+2)-1 公式推导如下：（注意An-1与A(n-1)区别） 斐波那契数列：1、1、2、3、5、8、13、21、……An 则:a1=1,a2=1,a3=2,a4=3,a5=5,……,an。 求和：Sn=a1+a2+a3+……+An Sn=1+a1+a2+a3+……+An-1 因为a2等于1，所以Sn=a2+a1+a2+a3+……+An-1 即：Sn=a2+a1+a2+a3+……+An-1Sn=a3+a2+a3+……+An-1 Sn=a3+a2+a3+……+An-1Sn=a4+a3+……+An-1…… Sn=An+A(n-1)+An-1 即：Sn=A(n+1)+An-1=A(n+2)-1 证毕。

斐波那契数列平方求和的计算公式及其几何证明

斐波那契数列的递归定义形式如下： 又有其通项的计算公式为： 则其各项相加的平方和为：

1^2+1^2+2^2+3^2+5^2+8^2=8×13

∑na2n=a21+a22+…+a2n=anan+1 ∑nan2=a12+a22+…+an2=anan+1 如果则是，以几何的手段证明：12+12+22+32+52+82=8×1312+12+22+32+52+82=8×13

2 是 1+1 构成的新的长方形的长； a1^2+a2^2得 1*2 的矩形；在此基础上右加上 2^2 的正方形；