첫 n개의 양의 홀수는 다음과 같은 식으로 구할 수 있다.

1 + 3 + ⋯ + (2n - 1)

= (1 + 2 + 3 + 4 + ⋯ + (2n - 1) + 2n) - (2 + 4 + ⋯ + 2n)

= - n(n + 1) = n²

또 다른 중요한 공식으로 2의 거듭제곱의 합 공식이 있다. 이 공식은 첫 번째 튜토리얼에서 이미 사용한 적이 있다.

1 + 2 + 2² + ⋯ + 2ⁿ = 2ⁿ⁺¹ - 1

(2)

이제 알고리즘 분석과 관련된 첫 번째 예제를 살펴보자.

체스의 발명 체스는 수백년 전, 인도 북서부의 샤시라는 성현이 발명한 것으로 알려져 있다. 자신이 발명한 체스를 임금님에게 가져갔을 때 임금님은 체스 게임을 너무 좋아해 샤시가 원하는 것은 뭐든지 들어주겠다고 했다. 샤시는 밀을 다음과 같은 식으로 받고 싶다고 말했다. 첫째 날에는 체스판의 첫째 칸에 밀 한 톨, 둘째 날에는 둘째 칸에 두 톨, 셋째 날에는 네 톨, 넷째 날에는 여덟 톨을 받는 식으로 64개 칸을 모두 채울 때까지 받는 식이다. 이런 요구는 좋은 것이었을까?