수학(mathematics) 에서, 합계 (summation )는, 더해지는-숫자 (addends ) 또는 합해지는-숫자 (summands )로 불리는, 숫자의 임의의 종류의 수열의 덧셈입니다; 그 결과는 그들의 합 (sum ) 또는 총합 (total )입니다. 숫자 외에도, 값의 다른 유형: 함수, 벡터, 행렬, 다항식 및, 일반적으로 "+"로 표시된 연산이 정의되는 수학적 대상의 임의의 유형의 원소는 마찬가지로 합해질 수 있습니다.
무한 수열(infinite sequence) 의 합은 급수(series) 로 불립니다. 그들은 극한(limit) 의 개념을 포함하고, 이 기사에서 고려하지 않습니다.
명시적 수열의 합은 덧셈의 연속으로 표시됩니다. 예를 들어, [1, 2, 4, 2] 의 합은 1 + 2 + 4 + 2 로 표시되고, 결과는 9, 즉, 1 + 2 + 4 + 2 = 9 입니다. 덧셈은 결합적(associative) 이고 교환적(commutative) 이기 때문에, 괄호가 필요하지 않고, 그 결과는 더해지는-숫자의 순서에 의존하지 않습니다. 오직 한 원소의 수열의 합은 이 원소 자체가 됩니다. 빈 수열 (0개의 원소를 갖는 수열)은, 관례에 의해, 0이 됩니다.
매우 자주, 수열의 원소는, 규칙적인 패턴을 통해, 수열에서 그들의 위치의 함수(function) 로, 정의됩니다. 간단한 패턴에 대해, 긴 수열의 합은 대부분의 합하는-숫자를 생략-부호(...)로 대체함으로써 표현될 수 있을 것입니다. 예를 들어, 처음 100개의 자연수의 합은 1 + 2 + 3 + 4 + ⋅⋅⋅ + 99 + 100 으로 쓸 수 있을 것입니다. 그렇지 않으면, 합은 Σ 표기법(Σ notation) 을 사용함으로써 표시되며, 여기서
∑
{\displaystyle \textstyle \sum }
은 확대된 대문자 그리스 문자(Greek letter) 시그마(sigma) 입니다. 예를 들어, 첫 n 개의 자연수의 합은
∑
i
=
1
n
i
{\displaystyle \textstyle \sum _{i=1}^{n}i}
으로 표시됩니다.
긴 합, 및 변하는 길이의 합에 대해 (생략-부호 또는 Σ 표기법과 함께 정의된), 그것은 결과에 대해 닫힌-형식 표현(closed-form expression) 을 찾는 것이 공통적인 문제입니다. 예를 들어,[a]
∑
i
=
1
n
i
=
n
(
n
+
1
)
2
.
{\displaystyle \sum _{i=1}^{n}i={\frac {n(n+1)}{2}}.}
비록 그러한 공식이 항상 존재하지 않을지라도, 많은 합 공식이 발견되어 왔습니다. 가장 공통적이고 기초적인 것들 중 일부가 이 기사에서 나열됩니다.
Notation
Capital-sigma notation
The summation symbol
수학적 표기법은 많은 비슷한 항들의 합을 간결하게 나타내는 기호: 합계 기호 ,
∑
{\displaystyle \textstyle \sum }
, 똑바른 대문자 그리스 문자 시그마(Sigma) 의 확장된 형식을 사용합니다. 이것은 다음으로 정의됩니다:
∑
i
=
m
n
a
i
=
a
m
+
a
m
+
1
+
a
m
+
2
+
⋯
+
a
n
−
1
+
a
n
{\displaystyle \sum _{i\mathop {=} m}^{n}a_{i}=a_{m}+a_{m+1}+a_{m+2}+\cdots +a_{n-1}+a_{n}}
여기서 i 는 합계의 인덱스 (index of summation )를 나타냅니다; ai 는 급수에서 각 연속적인 항을 나타내는 인덱스된 변수입니다; m 은 합계의 낮은 경계 (lower bound of summation )이고, n 은 합계의 높은 경계 (upper bound of summation )입니다. 합계 기호 아래의 "i = m" 은 인덱스 i 가 m 과 같게 시작함을 의미합니다. 인덱스, i 는 각 연속 항에 대해 1씩 증가하고, i = n 일 때 중지합니다.[b]
여기서 제곱의 합계를 보여주는 예제입니다:
∑
i
=
3
6
i
2
=
3
2
+
4
2
+
5
2
+
6
2
=
86.
{\displaystyle \sum _{i=3}^{6}i^{2}=3^{2}+4^{2}+5^{2}+6^{2}=86.}
비공식적 서술은, 다음에서 처럼, 그들이 문맥에서 명확할 때, 인덱스의 정의와 합계의 경계를 때때로 생략합니다:
∑
a
i
2
=
∑
i
=
1
n
a
i
2
.
{\displaystyle \sum a_{i}^{2}=\sum _{i\mathop {=} 1}^{n}a_{i}^{2}.}
우리는 임의의 논리적 조건이 제공되는 이 표기법의 일반화를 종종 보고, 합은 조건을 만족시키는 모든 값에 걸쳐 취해지도록 의도됩니다. 여기서 일부 공통적인 예제입니다:
∑
0
≤
k
<
100
f
(
k
)
{\displaystyle \sum _{0\leq k<100}f(k)}
은 지정된 범위에서 모든 (정수)
k
{\displaystyle k}
에 걸쳐
f
(
k
)
{\displaystyle f(k)}
의 합입니다.
∑
x
∈
S
f
(
x
)
{\displaystyle \sum _{x\mathop {\in } S}f(x)}
은 집합
S
{\displaystyle S}
에서 모든 원소
x
{\displaystyle x}
에 걸쳐
f
(
x
)
{\displaystyle f(x)}
의 합입니다. 그리고
∑
d
|
n
μ
(
d
)
{\displaystyle \sum _{d|n}\;\mu (d)}
은
n
{\displaystyle n}
을 나누는 모든 양의 정수
d
{\displaystyle d}
에 걸쳐
μ
(
d
)
{\displaystyle \mu (d)}
의 합입니다.[c]
많은 시그마 기호의 사용을 일반화하는 방법이 역시 있습니다. 예를 들어,
∑
i
,
j
{\displaystyle \sum _{i,j}}
은 다음과 같습니다:
∑
i
∑
j
.
{\displaystyle \sum _{i}\sum _{j}.}
비슷한 표기법은, 그것이 수열의 곱(product) 을 나타낼 때, 적용되며, 이것은 그의 합계와 비슷하지만, 덧셈 대신에 곱셈 연산을 사용합니다 (그리고 빈 수열에 대해 0 대신에 1을 제공합니다). 같은 기본 구조가
∏
{\displaystyle \textstyle \prod }
와 함께 사용되며,
∑
{\displaystyle \textstyle \sum }
대체하여, 그리스 대문자 Pi 의 확장된 형식입니다.
Special cases
2개 미만의 숫자를 합하는 것이 가능합니다:
만약 합계가 하나의 더해지는 숫자
x
{\displaystyle x}
를 가지면, 평가된 합은
x
{\displaystyle x}
입니다.
만약 합계가 더해지는 숫자를 가지지 않으면, 평가된 합은 영(zero) 인데, 왜냐하면 영은 덧셈에 대해 항등원(identity) 이기 때문입니다. 이것은 빈 합 (empty sum ) 으로 알려져 있습니다.
이들 퇴보된 경우는 보통 합계 표기법이 특별한 경우에서 퇴보한 결과를 제공할 때 오직 사용됩니다.
예를 들어, 만약 위의 정의에서
n
=
m
{\displaystyle n=m}
이면, 합에서 오직 하나의 항이 있습니다; 만약
n
=
m
−
1
{\displaystyle n=m-1}
이면, 항이 없습니다.
Formal definition
합계는 다음으로 재귀적으로 정의될 수 있습니다:
∑
i
=
a
b
g
(
i
)
=
0
{\displaystyle \sum _{i=a}^{b}g(i)=0}
{\displaystyle }
, b < a 에 대해.
∑
i
=
a
b
g
(
i
)
=
g
(
b
)
+
∑
i
=
a
b
−
1
g
(
i
)
{\displaystyle \sum _{i=a}^{b}g(i)=g(b)+\sum _{i=a}^{b-1}g(i)}
, b ≥ a 에 대해.
Measure theory notation
측정(measure) 과 적분(integration) 이론의 표기법에서, 합은 한정 적분(definite integral) 으로 표현될 수 있습니다:
∑
k
=
a
b
f
(
k
)
=
∫
[
a
,
b
]
f
d
μ
{\displaystyle \sum _{k\mathop {=} a}^{b}f(k)=\int _{[a,b]}f\,d\mu }
여기서
[
a
,
b
]
{\displaystyle [a,b]}
는
a
{\displaystyle a}
로부터
b
{\displaystyle b}
까지 정수의 부분 집합이고,
μ
{\displaystyle \mu }
는 셈 측정(counting measure) 입니다.
Calculus of finite differences
구간(interval) [m , n ] 에서 정수에 걸쳐 정의된 함수 f 가 주어지면, 우리는 다음을 가집니다:
f
(
n
)
−
f
(
m
)
=
∑
i
=
m
n
−
1
(
f
(
i
+
1
)
−
f
(
i
)
)
.
{\displaystyle f(n)-f(m)=\sum _{i=m}^{n-1}(f(i+1)-f(i)).}
이것은 미적분학의 기본 정리(fundamental theorem of calculus) 의 유한 차이의 미적분학(calculus of finite differences) 의 유사체이며, 이것은 다음을 말합니다:
f
(
n
)
−
f
(
m
)
=
∫
m
n
f
′
(
x
)
d
x
,
{\displaystyle f(n)-f(m)=\int _{m}^{n}f'(x)\,dx,}
여기서
f
′
(
x
)
=
lim
h
→
0
f
(
x
+
h
)
−
f
(
x
)
h
{\displaystyle f'(x)=\lim _{h\to 0}{\frac {f(x+h)-f(x)}{h}}}
은 f 의 도함수(derivative) 입니다.
위의 방정식의 응용의 예제는 다음입니다:
n
k
=
∑
i
=
0
n
−
1
(
(
i
+
1
)
k
−
i
k
)
.
{\displaystyle n^{k}=\sum _{i=0}^{n-1}\left((i+1)^{k}-i^{k}\right).}
이항 정리(binomial theorem) 를 사용하면, 이것은 다음으로 다시-쓸 수 있을 것입니다:
n
k
=
∑
i
=
0
n
−
1
(
∑
j
=
0
i
−
1
(
k
j
)
x
j
)
.
{\displaystyle n^{k}=\sum _{i=0}^{n-1}\left(\sum _{j=0}^{i-1}{\binom {k}{j}}x^{j}\right).}
위의 공식은 다음에 의해 정의된 차이 연산자(difference operator)
Δ
{\displaystyle \Delta }
의 역함에 대해 보다 공통적으로 사용됩니다:
Δ
(
f
)
(
n
)
=
f
(
n
+
1
)
−
f
(
n
)
,
{\displaystyle \Delta (f)(n)=f(n+1)-f(n),}
여기서 f 는 비-음의 정수에 대해 정의된 함수입니다.
따라서, 그러한 함수 f 가 주어지면, 문제는 f 의 역차이(antidifference) , 즉
Δ
F
=
f
,
{\displaystyle \Delta F=f,}
, 즉,
F
(
n
+
1
)
−
F
(
n
)
=
f
(
n
)
{\displaystyle F(n+1)-F(n)=f(n)}
를 만족하는 함수
F
=
Δ
−
1
f
{\displaystyle F=\Delta ^{-1}f}
를 계산하는 것입니다.
이 함수는 상수의 덧셈까지 정의되고, 다음으로 선택될 수 있을 것입니다:[1]
F
(
n
)
=
∑
i
=
0
n
−
1
f
(
i
)
.
{\displaystyle F(n)=\sum _{i=0}^{n-1}f(i).}
그러한 합에 대해 닫힌-형식 표현(closed-form expression) 이 항상 있지는 않지만, 파울하버의 공식(Faulhaber’s formula) 은
f
(
n
)
=
n
k
{\displaystyle f(n)=n^{k}}
의 경우 및, n 의 모든 각 다항 함수(polynomial function) 에 대해 선형성(linearity) 에 의해 닫힌 형식을 제공합니다.
Approximation by definite integrals
많은 그러한 근사는, 합과 적분(integral) 사이의 다음 연결에 의해 얻어질 수 있으며, 이것은 임의의 것에 대해 유지됩니다:
증가하는(increasing) 함수 f :
∫
s
=
a
−
1
b
f
(
s
)
d
s
≤
∑
i
=
a
b
f
(
i
)
≤
∫
s
=
a
b
+
1
f
(
s
)
d
s
.
{\displaystyle \int _{s=a-1}^{b}f(s)\ ds\leq \sum _{i=a}^{b}f(i)\leq \int _{s=a}^{b+1}f(s)\ ds.}
감소하는(decreasing) 함수 f :
∫
s
=
a
b
+
1
f
(
s
)
d
s
≤
∑
i
=
a
b
f
(
i
)
≤
∫
s
=
a
−
1
b
f
(
s
)
d
s
.
{\displaystyle \int _{s=a}^{b+1}f(s)\ ds\leq \sum _{i=a}^{b}f(i)\leq \int _{s=a-1}^{b}f(s)\ ds.}
보다 일반적인 근사에 대해, 오일러–매클로린 공식(Euler–Maclaurin formula) 을 참조하십시오.
더해지는 숫자가 인덱스의 적분-가능한(integrable) 함수에 의해 주어지는 (또는 보간될-수 있는) 합계에 대해, 합계는 대응하는 명확한 적분의 정의에서 발생하는 리만 합(Riemann sum) 으로 해석될 수 있습니다. 우리는 그러므로 다음과 같은 예제를 기대할 수 있습니다:
b
−
a
n
∑
i
=
0
n
−
1
f
(
a
+
i
b
−
a
n
)
≈
∫
a
b
f
(
x
)
d
x
,
{\displaystyle {\frac {b-a}{n}}\sum _{i=0}^{n-1}f\left(a+i{\frac {b-a}{n}}\right)\approx \int _{a}^{b}f(x)\ dx,}
왜냐하면 오른쪽 변은 정의에 의해 왼쪽 변의
n
→
∞
{\displaystyle n\to \infty }
에 대한 극한이기 때문입니다. 어쨌든, 주어진 합에 대해 n 은 고정되고, f 에 대한 추가 가정없이 위의 근사에서 오차에 대해 거의 말할 수 없습니다: 넓게 진동하는 함수에 대해 리만 합은 리만 적분으로부터 임의로 멀리 떨어질 수 있는 것은 분명합니다.
Identities
아래 공식은 유한 합을 포함합니다; 삼각 함수(trigonometric function) 또는 다른 초월 함수(transcendental function) 를 포함하는 표현의 무한 합계 또는 유한 합계에 대해, 수학적 급수의 목록(list of mathematical series) 을 참조하십시오.
General identities
∑
n
=
s
t
C
⋅
f
(
n
)
=
C
⋅
∑
n
=
s
t
f
(
n
)
{\displaystyle \sum _{n=s}^{t}C\cdot f(n)=C\cdot \sum _{n=s}^{t}f(n)\quad }
(분배성(distributivity) )
∑
n
=
s
t
f
(
n
)
±
∑
n
=
s
t
g
(
n
)
=
∑
n
=
s
t
(
f
(
n
)
±
g
(
n
)
)
{\displaystyle \sum _{n=s}^{t}f(n)\pm \sum _{n=s}^{t}g(n)=\sum _{n=s}^{t}\left(f(n)\pm g(n)\right)\quad }
(교환성(commutativity) 및 결합성(associativity) )
∑
n
=
s
t
f
(
n
)
=
∑
n
=
s
+
p
t
+
p
f
(
n
−
p
)
{\displaystyle \sum _{n=s}^{t}f(n)=\sum _{n=s+p}^{t+p}f(n-p)\quad }
(인덱스 이동)
∑
n
∈
B
f
(
n
)
=
∑
m
∈
A
f
(
σ
(
m
)
)
,
{\displaystyle \sum _{n\in B}f(n)=\sum _{m\in A}f(\sigma (m)),\quad }
유한 집합 A 에서 유한 집합 B 위로의 전단사(bijection) σ에 대하여 (인덱스 변경); 이것은 이전 공식을 일반화합니다.
∑
n
=
s
t
f
(
n
)
=
∑
n
=
s
j
f
(
n
)
+
∑
n
=
j
+
1
t
f
(
n
)
{\displaystyle \sum _{n=s}^{t}f(n)=\sum _{n=s}^{j}f(n)+\sum _{n=j+1}^{t}f(n)\quad }
(결합성(associativity) 을 사용하여, 합을 분리함)
∑
n
=
a
b
f
(
n
)
=
∑
n
=
0
b
f
(
n
)
−
∑
n
=
0
a
−
1
f
(
n
)
{\displaystyle \sum _{n=a}^{b}f(n)=\sum _{n=0}^{b}f(n)-\sum _{n=0}^{a-1}f(n)\quad }
(이전 공식의 변형)
∑
i
=
k
0
k
1
∑
j
=
l
0
l
1
a
i
,
j
=
∑
j
=
l
0
l
1
∑
i
=
k
0
k
1
a
i
,
j
{\displaystyle \sum _{i=k_{0}}^{k_{1}}\sum _{j=l_{0}}^{l_{1}}a_{i,j}=\sum _{j=l_{0}}^{l_{1}}\sum _{i=k_{0}}^{k_{1}}a_{i,j}\quad }
(다시, 교환성 및 결합성)
∑
k
≤
j
≤
i
≤
n
a
i
,
j
=
∑
i
=
k
n
∑
j
=
k
i
a
i
,
j
=
∑
j
=
k
n
∑
i
=
j
n
a
i
,
j
=
∑
j
=
0
n
−
k
∑
i
=
k
n
−
j
a
i
+
j
,
i
{\displaystyle \sum _{k\leq j\leq i\leq n}a_{i,j}=\sum _{i=k}^{n}\sum _{j=k}^{i}a_{i,j}=\sum _{j=k}^{n}\sum _{i=j}^{n}a_{i,j}=\sum _{j=0}^{n-k}\sum _{i=k}^{n-j}a_{i+j,i}\quad }
(교환성 및 결합서의 또 다른 응용)
∑
n
=
0
2
t
+
1
f
(
n
)
=
∑
n
=
0
t
f
(
2
n
)
+
∑
n
=
0
t
f
(
2
n
+
1
)
{\displaystyle \sum _{n=0}^{2t+1}f(n)=\sum _{n=0}^{t}f(2n)+\sum _{n=0}^{t}f(2n+1)\quad }
(합을 홀수 및 짝수 부분으로 나누고, 인덱스를 변경함)
(
∑
i
=
0
n
a
i
)
(
∑
j
=
0
n
b
j
)
=
∑
i
=
0
n
∑
j
=
0
n
a
i
b
j
{\displaystyle \left(\sum _{i=0}^{n}a_{i}\right)\left(\sum _{j=0}^{n}b_{j}\right)=\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}b_{j}\quad }
(분배성(distributivity) )
∑
i
=
s
m
∑
j
=
t
n
a
i
c
j
=
(
∑
i
=
s
m
a
i
)
(
∑
j
=
t
n
c
j
)
{\displaystyle \sum _{i=s}^{m}\sum _{j=t}^{n}{a_{i}}{c_{j}}=\left(\sum _{i=s}^{m}a_{i}\right)\left(\sum _{j=t}^{n}c_{j}\right)\quad }
(분배성은 인수분해를 허용합니다)
∑
n
=
s
t
log
b
f
(
n
)
=
log
b
∏
n
=
s
t
f
(
n
)
{\displaystyle \sum _{n=s}^{t}\log _{b}f(n)=\log _{b}\prod _{n=s}^{t}f(n)\quad }
(곱의 로그(logarithm) 는 인수의 로그의 합입니다)
C
∑
n
=
s
t
f
(
n
)
=
∏
n
=
s
t
C
f
(
n
)
{\displaystyle C^{\sum \limits _{n=s}^{t}f(n)}=\prod _{n=s}^{t}C^{f(n)}\quad }
(합의 지수(exponential) 는 더해지는-숫자의 지수의 곱입니다)
Powers and logarithm of arithmetic progressions
∑
i
=
1
n
c
=
n
c
{\displaystyle \sum _{i=1}^{n}c=nc\quad }
i 에 의존하지 않는 모든 각 c 에 대해
∑
i
=
0
n
i
=
∑
i
=
1
n
i
=
n
(
n
+
1
)
2
{\displaystyle \sum _{i=0}^{n}i=\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}\qquad }
(가장-간단한 산술 진행(arithmetic progression) 의 합, n 처음 자연수(natural number) 로 구성됩니다)[2] [full citation needed ]
∑
i
=
1
n
(
2
i
−
1
)
=
n
2
{\displaystyle \sum _{i=1}^{n}(2i-1)=n^{2}\qquad }
(처음 홀의 자연수의 합)
∑
i
=
0
n
2
i
=
n
(
n
+
1
)
{\displaystyle \sum _{i=0}^{n}2i=n(n+1)\qquad }
(처음 짝의 자연수의 합)
∑
i
=
1
n
log
i
=
log
n
!
{\displaystyle \sum _{i=1}^{n}\log i=\log n!\qquad }
(로그(logarithm) 의 합은 곱의 로그입니다)
∑
i
=
0
n
i
2
=
n
(
n
+
1
)
(
2
n
+
1
)
6
=
n
3
3
+
n
2
2
+
n
6
{\displaystyle \sum _{i=0}^{n}i^{2}={\frac {n(n+1)(2n+1)}{6}}={\frac {n^{3}}{3}}+{\frac {n^{2}}{2}}+{\frac {n}{6}}\qquad }
(처음 제곱(squares) 의 합, 제곱 피라미드 숫자(square pyramidal number) 를 참조하십시오.)[2]
∑
i
=
0
n
i
3
=
(
∑
i
=
0
n
i
)
2
=
(
n
(
n
+
1
)
2
)
2
=
n
4
4
+
n
3
2
+
n
2
4
{\displaystyle \sum _{i=0}^{n}i^{3}=\left(\sum _{i=0}^{n}i\right)^{2}=\left({\frac {n(n+1)}{2}}\right)^{2}={\frac {n^{4}}{4}}+{\frac {n^{3}}{2}}+{\frac {n^{2}}{4}}\qquad }
(니코마코스의 정리(Nicomachus's theorem) )[2]
보다 일반적으로,
∑
i
=
0
n
i
p
=
(
n
+
1
)
p
+
1
p
+
1
+
∑
k
=
1
p
B
k
p
−
k
+
1
(
p
k
)
(
n
+
1
)
p
−
k
+
1
,
{\displaystyle \sum _{i=0}^{n}i^{p}={\frac {(n+1)^{p+1}}{p+1}}+\sum _{k=1}^{p}{\frac {B_{k}}{p-k+1}}{p \choose k}(n+1)^{p-k+1},}
여기서
B
k
{\displaystyle B_{k}}
는 베르누이 숫자(Bernoulli number) (즉 파울하버 공식(Faulhaber's formula) )를 나타냅니다.
Summation index in exponents
다음 합계에 대해, a는 1과 다른 값으로 가정됩니다.
∑
i
=
0
n
−
1
a
i
=
1
−
a
n
1
−
a
{\displaystyle \sum _{i=0}^{n-1}a^{i}={\frac {1-a^{n}}{1-a}}\quad }
(기하 진행(geometric progression) 의 합)
∑
i
=
0
n
−
1
1
2
i
=
2
−
1
2
n
−
1
{\displaystyle \sum _{i=0}^{n-1}{\frac {1}{2^{i}}}=2-{\frac {1}{2^{n-1}}}\quad }
(a = 1/2 에 대해 특별한 경우)
∑
i
=
0
n
−
1
i
a
i
=
a
−
n
a
n
+
(
n
−
1
)
a
n
+
1
(
1
−
a
)
2
{\displaystyle \sum _{i=0}^{n-1}ia^{i}={\frac {a-na^{n}+(n-1)a^{n+1}}{(1-a)^{2}}}\quad }
(기하 진행의 a 에 관한 도함수의 a 배)
∑
i
=
0
n
−
1
(
b
+
i
d
)
a
i
=
b
∑
i
=
0
n
−
1
a
i
+
d
∑
i
=
0
n
−
1
i
a
i
=
b
(
1
−
a
n
1
−
a
)
+
d
(
a
−
n
a
n
+
(
n
−
1
)
a
n
+
1
(
1
−
a
)
2
)
=
b
(
1
−
a
n
)
−
(
n
−
1
)
d
a
n
1
−
a
+
d
a
(
1
−
a
n
−
1
)
(
1
−
a
)
2
{\displaystyle {\begin{aligned}\sum _{i=0}^{n-1}\left(b+id\right)a^{i}&=b\sum _{i=0}^{n-1}a^{i}+d\sum _{i=0}^{n-1}ia^{i}\\&=b\left({\frac {1-a^{n}}{1-a}}\right)+d\left({\frac {a-na^{n}+(n-1)a^{n+1}}{(1-a)^{2}}}\right)\\&={\frac {b(1-a^{n})-(n-1)da^{n}}{1-a}}+{\frac {da(1-a^{n-1})}{(1-a)^{2}}}\end{aligned}}}
(산술–기하 수열(arithmetico–geometric sequence) 의 합)
Binomial coefficients and factorials
이항 계수를 포함하는 매우 많은 합계 항등식이 존재합니다 (구체적 수학 (Concrete Mathematics ) 의 전체 챕터는 바로 기본 기법에 사용됩니다). 가장 기본적인 것들의 일부는 다음입니다.
Involving the binomial theorem
∑
i
=
0
n
(
n
i
)
a
n
−
i
b
i
=
(
a
+
b
)
n
,
{\displaystyle \sum _{i=0}^{n}{n \choose i}a^{n-i}b^{i}=(a+b)^{n},\quad }
이항 정리(binomial theorem)
∑
i
=
0
n
(
n
i
)
=
2
n
,
{\displaystyle \sum _{i=0}^{n}{n \choose i}=2^{n}\quad ,}
a = b = 1 인 특별한 경우
∑
i
=
0
n
(
n
i
)
p
i
(
1
−
p
)
n
−
i
=
1
,
{\displaystyle \sum _{i=0}^{n}{n \choose i}p^{i}(1-p)^{n-i}=1,\quad }
p = a = 1 – b 인 특별한 경우, 이것은
0
≤
p
≤
1
{\displaystyle 0\leq p\leq 1}
에 대해 이항 분포(binomial distribution) 의 합을 나타냅니다
∑
i
=
0
n
i
(
n
i
)
=
n
(
2
n
−
1
)
,
{\displaystyle \sum _{i=0}^{n}i{n \choose i}=n(2^{n-1}),\quad }
이항 정리의 a 에 관한 도함수(derivative) 의 a = b = 1 에서 값
∑
i
=
0
n
(
n
i
)
i
+
1
=
2
n
+
1
−
1
n
+
1
,
{\displaystyle \sum _{i=0}^{n}{\frac {n \choose i}{i+1}}={\frac {2^{n+1}-1}{n+1}},\quad }
이항 정리의 a 에 관한 역도함수(antiderivative) 의 a = b = 1 에서 값
Involving permutation numbers
다음 합계에서,
n
P
k
{\displaystyle {}_{n}P_{k}}
는 n 의 k -순열 의 숫자입니다.
∑
i
=
0
n
i
P
k
(
n
i
)
=
n
P
k
(
2
n
−
k
)
{\displaystyle \sum _{i=0}^{n}{}_{i}P_{k}{n \choose i}={}_{n}P_{k}(2^{n-k})\quad }
∑
i
=
1
n
i
+
k
P
k
+
1
=
∑
i
=
1
n
∏
j
=
0
k
(
i
+
j
)
=
(
n
+
k
+
1
)
!
(
n
−
1
)
!
(
k
+
2
)
{\displaystyle \sum _{i=1}^{n}{}_{i+k}P_{k+1}=\sum _{i=1}^{n}\prod _{j=0}^{k}(i+j)={\frac {(n+k+1)!}{(n-1)!(k+2)}}\quad }
∑
i
=
0
n
i
!
⋅
(
n
i
)
=
∑
i
=
0
n
n
P
i
=
⌊
n
!
⋅
e
⌋
,
n
∈
Z
+
{\displaystyle \sum _{i=0}^{n}i!\cdot {n \choose i}=\sum _{i=0}^{n}{}_{n}P_{i}=\lfloor n!\cdot e\rfloor ,\quad n\in \mathbb {Z} ^{+}}
이고,
⌊
x
⌋
{\displaystyle \lfloor x\rfloor }
는 바닥 함수(floor function) 을 나타냅니다.
Others
∑
k
=
0
m
(
n
+
k
n
)
=
(
n
+
m
+
1
n
+
1
)
{\displaystyle \sum _{k=0}^{m}\left({\begin{array}{c}n+k\\n\\\end{array}}\right)=\left({\begin{array}{c}n+m+1\\n+1\\\end{array}}\right)}
∑
i
=
k
n
(
i
k
)
=
(
n
+
1
k
+
1
)
{\displaystyle \sum _{i=k}^{n}{i \choose k}={n+1 \choose k+1}}
∑
i
=
0
n
i
⋅
i
!
=
(
n
+
1
)
!
−
1
{\displaystyle \sum _{i=0}^{n}i\cdot i!=(n+1)!-1}
∑
i
=
0
n
(
m
+
i
−
1
i
)
=
(
m
+
n
n
)
{\displaystyle \sum _{i=0}^{n}{m+i-1 \choose i}={m+n \choose n}}
∑
i
=
0
n
(
n
i
)
2
=
(
2
n
n
)
{\displaystyle \sum _{i=0}^{n}{n \choose i}^{2}={2n \choose n}}
Harmonic numbers
∑
i
=
1
n
1
i
=
H
n
{\displaystyle \sum _{i=1}^{n}{\frac {1}{i}}=H_{n}\quad }
(이것은 n 번째 조화 숫자(Harmonic number) 입니다)
∑
i
=
1
n
1
i
k
=
H
n
k
{\displaystyle \sum _{i=1}^{n}{\frac {1}{i^{k}}}=H_{n}^{k}\quad }
(이것은 일반화된 조화 숫자(Generalized harmonic number) 입니다)
Growth rates
다음은 (세타 표기법(theta notation) 사용을 사용하여) 유용한 근사(approximation) 입니다:
∑
i
=
1
n
i
c
∈
Θ
(
n
c
+
1
)
{\displaystyle \sum _{i=1}^{n}i^{c}\in \Theta (n^{c+1})\quad }
−1보다 큰 실수 c 에 대해
∑
i
=
1
n
1
i
∈
Θ
(
log
e
n
)
{\displaystyle \sum _{i=1}^{n}{\frac {1}{i}}\in \Theta (\log _{e}n)\quad }
(조화 숫자(Harmonic number) 를 참조하십시오)
∑
i
=
1
n
c
i
∈
Θ
(
c
n
)
{\displaystyle \sum _{i=1}^{n}c^{i}\in \Theta (c^{n})\quad }
1보다 큰 실수 c 에 대해
∑
i
=
1
n
log
(
i
)
c
∈
Θ
(
n
⋅
log
(
n
)
c
)
{\displaystyle \sum _{i=1}^{n}\log(i)^{c}\in \Theta (n\cdot \log(n)^{c})\quad }
비-음의(non-negative) 실수 c 에 대해
∑
i
=
1
n
log
(
i
)
c
⋅
i
d
∈
Θ
(
n
d
+
1
⋅
log
(
n
)
c
)
{\displaystyle \sum _{i=1}^{n}\log(i)^{c}\cdot i^{d}\in \Theta (n^{d+1}\cdot \log(n)^{c})\quad }
비-음의 실수 c , d 에 대해
∑
i
=
1
n
log
(
i
)
c
⋅
i
d
⋅
b
i
∈
Θ
(
n
d
⋅
log
(
n
)
c
⋅
b
n
)
{\displaystyle \sum _{i=1}^{n}\log(i)^{c}\cdot i^{d}\cdot b^{i}\in \Theta (n^{d}\cdot \log(n)^{c}\cdot b^{n})\quad }
비-음의 실수 b > 1, c , d 에 대해
See also
Notes
^ For details, see Triangular number .
^ For a detailed exposition on summation notation, and arithmetic with sums, see Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). "Chapter 2: Sums". Concrete Mathematics: A Foundation for Computer Science (PDF) (2nd ed.). Addison-Wesley Professional. ISBN 978-0201558029 . [permanent dead link ]
^ Although the name of the dummy variable does not matter (by definition), one usually uses letters from the middle of the alphabet (
i
{\displaystyle i}
through
q
{\displaystyle q}
) to denote integers, if there is a risk of confusion. For example, even if there should be no doubt about the interpretation, it could look slightly confusing to many mathematicians to see
x
{\displaystyle x}
instead of
k
{\displaystyle k}
in the above formulae involving
k
{\displaystyle k}
. See also typographical conventions in mathematical formulae .
References
^ Handbook of Discrete and Combinatorial Mathematics , Kenneth H. Rosen, John G. Michaels, CRC Press, 1999, ISBN 0-8493-0149-1 .
^ a b c CRC, p 52
External links