์ด ๊ณ์ฐ๊ธฐ์ ๊ธฐ๋ฅ
ํน์ ์์ด์ ํฉ(ฮฃ) ๊ณ์ฐ๊ธฐ๋ ์ ํํ 'ํน์' ์์ด์ ์ฒ์ n๊ฐ ํญ์ ํฉ์, ๊ทธ ์์ด์ ๋์ํ๋ ์ ํํ ๋ซํ ํํ(closed-form) ๊ณต์์ผ๋ก ๊ณ์ฐํฉ๋๋ค. ํญ์ ํ๋์ฉ ๋ํ๋ ๋์ ์ ์๋ ค์ง ํญ๋ฑ์์ ์ ์ฉํ๋ฏ๋ก, n์ด ์๋ฌด๋ฆฌ ์ปค๋ ๋ต์ด ์ฆ์ ๊ทธ๋ฆฌ๊ณ ์ ํํ๊ฒ ๋์ต๋๋ค. ๋จ์๋ ์๊ณ ๊ตญ๊ฐ๋ณ ๊ท์ ๋ ์ ์ฉ๋์ง ์๋ ์์ ์ํ ๋๊ตฌ๋ผ์ ์ด๋์๋ ๋์ผํ๊ฒ ์๋ํฉ๋๋ค.
7๊ฐ์ง ์์ด
k = 1๋ถํฐ n๊น์ง ํฉ์ฐํ ํญ์ ์์ผ๋ก ์๋ ์ค ํ๋๋ฅผ ์ ํํ ์ ์์ต๋๋ค.
$$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$$ $$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$$ $$\sum_{k=1}^{n} k^3 = \frac{n^2(n+1)^2}{4}$$ $$\sum_{k=1}^{n} k(k+1) = \frac{n(n+1)(n+2)}{3}$$ $$\sum_{k=1}^{n} \frac{1}{k(k+1)} = \frac{n}{n+1}$$ $$\sum_{k=1}^{n} k(k+1)(k+2) = \frac{n(n+1)(n+2)(n+3)}{4}$$ ๊ทธ๋ฆฌ๊ณ $$\sum_{k=1}^{n} \frac{1}{k(k+1)(k+2)} = \frac{n(n+3)}{4(n+1)(n+2)}$$
์ฒซ์งธ, ๋์งธ, ์ ์งธ, ๋ท์งธ, ์ฌ์ฏ์งธ ์์ ํญ์ ์ ์๋ก ๋จ์ด์ง๋ฉฐ, ๋ค์ฏ์งธ์ ์ผ๊ณฑ์งธ ์์ ๋ง์๊ธ์(telescoping series)๋ก์ ๊ทธ ํฉ์ด 0๊ณผ 1 ์ฌ์ด์ ๊ฐ๋ง์ ๊ฐ์ง๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
๋๋กญ๋ค์ด์์ ์์ด์ ๊ณ ๋ฅด๊ณ , ํญ์ ๊ฐ์ n(1, 2, 3 โฆ ๊ฐ์ ์์ ์ ์)์ ์ ๋ ฅํ ๋ค, ํ์ํ ์ ํจ์ซ์ ์๋ฆฟ์๋ฅผ ์ ํํ๋ฉด ํฉ์ ๋ฐ๋ก ํ์ธํ ์ ์์ต๋๋ค. ์ ๋ฐ๋ ์ ํ์ ํ๋ฉด ํ์์ฉ์ผ ๋ฟ์ด๋ฉฐ, ๊ธฐ๋ฐ์ด ๋๋ ๋ซํ ๊ณต์์ ์ํ์ ์ผ๋ก ์ ํํฉ๋๋ค.
๊ณ์ฐ ์์
\(\sum k^3\)์ ์ ํํ๊ณ \(n = 9\)๋ก ๋๋ฉด, ๊ณต์์ ๋ฐ๋ผ $$\frac{9^2 \times 10^2}{4} = \frac{81 \times 100}{4} = \frac{8100}{4} = 2025$$๊ฐ ๋ฉ๋๋ค. ์ด๋ ์ ์๋ ค์ง ํญ๋ฑ์ \(1^3 + 2^3 + \cdots + 9^3 = 2025\)์ ์ ํํ ์ผ์นํฉ๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
์ ์ผ์ผ์ด ๋ํ์ง ์๊ณ ๊ณต์์ ์ฐ๋์? ๋ซํ ํํ ๊ณต์์ \(O(1)\)์ด๋ผ์ n์ด ์๋ฌด๋ฆฌ ์ปค๋ ์ฆ์ ์ ํํ ๊ฐ์ ์ฃผ๋ฉฐ, ๊ธด ๋ง์ ์์ ์๊ธฐ๋ ๋ฐ์ฌ๋ฆผ ์ค์ฐจ๋ ์์ต๋๋ค.
n์ด ์์ ์ ์๊ฐ ์๋๋ฉด ์ด๋ป๊ฒ ๋๋์? ํฉ์ฐ ์ง์ k๋ ์์ ์ ์ ์์์ ์์ง์ด๋ฏ๋ก, n์ 1 ์ด์์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ ์๋ก ๋ณด์ ๋ฉ๋๋ค.
์ 5๋ฒ๊ณผ 7๋ฒ ๊ฒฐ๊ณผ๋ 1๋ณด๋ค ์๋์? ๋ ์์ ๋ง์๊ธ์๋ก, ๋ถ๋ถํฉ์ด 1(\(\frac{1}{k(k+1)}\) ๊ฒฝ์ฐ)์ด๋ 1/4(\(\frac{1}{k(k+1)(k+2)}\) ๊ฒฝ์ฐ)์ ์ ์ ๊ฐ๊น์์ง์ง๋ง, ์ ํํ n์์๋ ๊ฒฐ์ฝ ๊ทธ ๊ทนํ๊ฐ์ ๋๋ฌํ์ง ์๊ธฐ ๋๋ฌธ์ ๋๋ค.