자연수의 합 공식과 삼각수 - soo:bak

작성일 :

자연수의 합이란?

1부터 n까지의 자연수의 합은 다음과 같이 정의됩니다:

\[\sum_{k=1}^{n} k = 1 + 2 + 3 + \dots + n\]

이 합을 단순히 반복문으로 계산하면 시간 복잡도가 \(O(n)\)이지만,

수학적 공식을 사용하면 \(O(1)\) 시간에 결과를 구할 수 있습니다.


공식의 유도

자연수의 합을 구하는 대표적인 방법은 수열을 대칭적으로 정렬하여 계산하는 것입니다.

1부터 10까지의 합을 예로 들어보겠습니다.


수열의 대칭 구조

수열을 두 줄로 나열하되, 한 줄은 정방향, 다른 한 줄은 역방향으로 배치합니다:

\[\begin{aligned} &1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 \\ +\;&10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 \end{aligned}\]


각 열의 합은 모두 11이며, 총 10쌍이 존재하므로:

\[(1 + 10) + (2 + 9) + (3 + 8) + \dots + (10 + 1) = 11 \times 10 = 110\]


이는 원래 수열을 두 번 더한 값이므로, 실제 합은 다음과 같습니다:

\[\frac{110}{2} = 55\]


일반식 도출

위 과정을 일반화하면 다음과 같습니다.

n개의 자연수를 정방향과 역방향으로 배치할 때, 각 쌍의 합은 \((n+1)\)이며, 총 \(n\)쌍이 존재합니다.

따라서:

\[2 \sum_{k=1}^{n} k = n(n+1)\]


이를 정리하면:

\[\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\]


이 공식은 수열을 대칭적으로 정렬하여 합을 계산하는 원리에서 도출됩니다.


삼각수(Triangular Number)란?

삼각수는 점을 정삼각형 모양으로 배치했을 때 생기는 점의 개수를 의미합니다.

예를 들어, 다음과 같은 배치를 생각할 수 있습니다:


1번째 삼각수:

1

•

2번째 삼각수:

1
2

•
• •

3번째 삼각수:

1
2
3

•
• •
• • •

4번째 삼각수:

1
2
3
4

•
• •
• • •
• • • •


각 층마다 점이 하나씩 더해지므로, \(n\)번째 삼각수는 다음과 같습니다:

\[T_n = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}\]

즉, 삼각수는 1부터 n까지의 자연수 합과 동일한 값을 가집니다.


삼각수의 기하학적 해석

\(n = 5\)일 때 삼각수 구조는 다음과 같이 표현됩니다:

1
2
3
4
5

    •
   • •
  • • •
 • • • •
• • • • •

총 점의 개수: \(1 + 2 + 3 + 4 + 5 = 15\)

공식으로 확인: \(\frac{5 \times 6}{2} = 15\)


이처럼 삼각수는 기하학적 구조를 통해 자연수 합 공식을 직관적으로 이해할 수 있는 수열입니다.


삼각수의 성질

삼각수는 다음과 같은 성질을 가집니다:

\[T_n = \frac{n(n+1)}{2}\] \[T_{n} - T_{n-1} = n\]

즉, 연속된 두 삼각수의 차이는 자연수 \(n\)과 같습니다.


삼각수는 누적합 구조, 반복 루프, 조합론 등 다양한 알고리즘 문제에서 자주 등장하는 수열입니다.


삼각수와 파스칼의 삼각형

삼각수는 파스칼의 삼각형(Pascal’s Triangle) 과 깊은 연관이 있습니다.


파스칼의 삼각형이란?

파스칼의 삼각형은 이항 계수를 삼각형 형태로 배열한 것으로, 각 수는 바로 위의 두 수의 합으로 구성됩니다:

1
2
3
4
5
6

              1                  
            1   1                
          1   2   1              
        1   3   3   1            
      1   4   6   4   1          
    1   5  10  10   5   1


삼각수와의 관계

파스칼의 삼각형에서 세 번째 대각선을 관찰하면 다음과 같은 수열을 발견할 수 있습니다:

\[1, 3, 6, 10, 15, 21, \dots\]


이 수들은 바로 삼각수입니다!


이를 조합 기호로 표현하면:

\[T_n = \binom{n+1}{2} = \frac{(n+1)!}{2!(n-1)!} = \frac{(n+1) \times n}{2} = \frac{n(n+1)}{2}\]


즉, \(n\)번째 삼각수는 \((n+1)\)개 중 2개를 선택하는 조합의 개수와 같습니다.


직관적 이해

이 관계는 다음과 같이 직관적으로 이해할 수 있습니다.

\(n+1\)개의 점 중 2개를 선택하여 선분을 만드는 경우의 수는:

  • 점들을 \(1, 2, 3, \dots, n+1\)로 번호를 매기면
  • 점 1에서 다른 점들로 가는 선분: \(n\)개
  • 점 2에서 나머지 점들로 가는 선분: \(n-1\)개
  • 점 3에서 나머지 점들로 가는 선분: \(n-2\)개
  • …
  • 총 \(n + (n-1) + (n-2) + \dots + 1 = T_n\)


이처럼 삼각수는 조합론의 관점에서도 자연스럽게 등장하는 수열입니다.


참고 : 조합(Combination)의 원리와 구현 - soo:bak


예제 코드 (C++)

공식을 활용하여 1부터 100까지의 합을 계산하는 코드는 다음과 같습니다:

1
2

int sum = 100 * (100 + 1) / 2;
cout << sum; // 출력: 5050


반복문 없이 \(O(1)\) 시간에 결과를 구할 수 있습니다.


마무리

자연수의 합 공식은 단순히 암기하는 것이 아니라, 수열의 대칭 구조를 통해 유도할 수 있는 수학적 원리입니다.


삼각수는 이 공식을 기하학적으로 해석한 개념으로, 각 층에 점을 쌓아가는 구조를 통해 자연수 합의 의미를 직관적으로 이해할 수 있습니다.


특히 삼각수는 파스칼의 삼각형의 세 번째 대각선으로 등장하며,

조합론의 관점에서 \((n+1)\)개 중 2개를 선택하는 경우의 수로도 해석됩니다.


이러한 수학적 구조는 알고리듬 설계와 복잡도 분석에서도 자주 활용되므로,

공식의 배경 원리와 다양한 해석을 이해하는 것이 중요합니다.


관련 글:

이 블로그의 다른 글