주어진 급수의 합을 구하려면 먼저 급수를 분석하여 알려진 급수인지, 혹은 여러 급수가 결합된 형태인지 판별할 수 있는 특징을 찾아야 합니다. 이번에 다룰 급수는 5, 12, 23, 38…입니다.
목표는 임의의 값 n에 대해 이 급수의 처음 n항의 합을 구하는 것입니다.
예제
n = 3일 때
합계 = 40
급수의 성질 분석
주어진 급수를 분석해 보면 인접한 항들 사이의 차이가 각각 7, 11, 15로, 4씩 일정하게 증가하는 등차수열을 이룹니다. 이러한 특징을 가진 급수를 이차 급수(quadratic series)라고 하며, 일반항을 n의 이차식으로 표현할 수 있습니다.
실제로 이 급수의 일반항은 T(n) = 2n² + n + 2이므로, 전체 합은 다음 세 부분의 합으로 분해할 수 있습니다.
- Σ2n² = 2 × n(n+1)(2n+1) / 6
- Σn = n(n+1) / 2
- Σ2 = 2n
이를 하나의 공식으로 정리하면 다음과 같습니다.
Sum = (2*(n*(n+1)*(2*n+1)/6)) + n*(n+1)/2 + 2*n
C 프로그램 예제
#include <stdio.h>
int main() {
int n = 6;
int sum = (2*(n*(n+1)*(2*n+1)/6)+(n*(n+1)/2)+(2*n));
printf("the sum of series till %d is %d", n,sum);
return 0;
}
실행 결과
the sum of series till 6 is 215
n = 6일 때 계산 결과는 215이며, 실제로 5 + 12 + 23 + 38 + 57 + 80 = 215와 일치합니다. 이처럼 이차 급수의 합 공식을 활용하면 반복문 없이도 O(1)의 시간 복잡도로 매우 빠르게 합을 구할 수 있다는 장점이 있습니다.