거듭 제곱의 합 

 우리가 고등학교 수열과정에 배우는 내용중 하나인 거듭제곱 공식에 대해서 배운다.

 사실 많은 사람들이 이 공식에 관해서 머리속에 박아 외우고 있는 사람들은 많지만 정작 이런 공식들이 어떻게 나오는 지에 관해서는 모르는 경우가 많다.

1~n까지 모든 자연수들의 합을 나타내면

다음과 같이 표기한다. 보통 시그마라고 읽는다.  보통 우리들은 이 공식들을 외우고 있다.

혹시 이 공식의 증명법을 모르시는 분들을 위해서 한번 정리해 보자면 1)식과 2)식을 더하면 3)식이 나오는데 이때 (n+1)의 갯수가 총 n개 존재한다.(1~n이 n개존재하므로) 따라서 n(n+1)이된다.

그리고 그식을 정리하면 마지막 공식이 톡하고 튀어나오게 되시겠다.

이런 것들을 정리해 보자면

그런데 이게 4일때는? 5일때는? 6일때는?... k일때는?.... 

넘나 복잡한 것

이제 우리가 하고자 하는 일은 아래의 식을 모든 정수 k에대해 n에 관한 식으로 나타내는 것이다.

사실 여기서부터가 재밌다. 어떤 점화관계가 주어지면 재귀적으로 쉽게 풀 수 있는 문제들이 있다. 이는 재귀적으로 정의하고 그것을 정리하면 n에관한 식을 손쉽게 표현하고 구할 수 있을 것이다. 

우리는 문제를 풀기 앞서서 아래의 공식을 배운 적 있을 것이다.

위와 같은 식이 성립함으로 인해서 우리는 이 식을 가지고 장난을 쳐 우리가 원하는 바를 이루어 낼 것이다. 

(이 식을 처음 보시는 분들은 이항 정리에 관하여 검색해 보세요)

우리가 원하는 바를 이루기 위해서는 k+1에 관한 식이 필요하다. 그 이유는 포스트를 쭉 읽다보면 이해 할 수 있을 것이다. (k를 k+1로 치환하도록 하자)

이제 이 식에서 

을 좌항으로 옮길 것이다. 그렇다면 아래와 같은 식이 나타난다.

그리고 우리는 이식을 보면 하고 싶은 짓이있을 것이다. 계차수열의 일반항을 구할 때 했던 방법. 이제부터 x에 1부터 n까지의 수를 대입해보도록 하자.

이제우리가 할일은? 

다 더하기

그러면 좌측항이 아주 이쁘게 정리되면서 아래와 같은 식을 얻을 수 있다.

우리가 구하고 싶은 것은 S(n,k)이므로 이것에 대해 정리하기 위해서 S(n,k)만 우항에 놔두고 모든 식을 좌항으로 옮기도록 하자. 그렇다면

짜란 이제 우리는 임의의 k가 주어졌을때 S(n,0)~S(n,k-1)을 사용해 k일때의 n에 관한 식으로 만들 수 있다.

즉 점화식을 완성한 것이다 ^ㅇ^

식을 정리해서 만들었으니 k=2일때 제대로 정리 되었는지 보자.

완젼 잘나오네요 ㅎㅎ

k=3일때랑 k=4일때도 해보세요. 저는 귀찮아서 하기싫어여…

사실 이 문제에 관해서 점화관계뿐만 아니라 일반항을 나타낼 수 있다. 베르누이 수를 이용해서라고... 

수학자가 아닌 내가 이해하기는 힘든 증명이라 링크만 달아 놓도록 하겠다. 

Faulhaber's formula

능력자 분들 중 이글을 보게 되는 분이 있다면 저것에 관해서 설명좀 부탁드려요..

이것과 관련된 알고리즘 문제 풀어보기

.

이걸 계산하는 프로그램을 원하시면 코멘트 달아주세요. 만들어 드리겠습니다.

참고

http://blog.naver.com/dalsapcho/20141141955