Sums of series (1+2+…+n, 1+2+4+…+2ⁿ); basic counting

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What is ⌈log₂ 26⌉, and what does it count? from Lesson 0.2.1
• Trace: int a = 3; a = a + a; a = a + 1; What is a? from Lesson 0.1.2
• How many characters does "A\tB" contain? from Lesson 0.1.1

1 · The Hook

🎣

A king promises a farmer rice: 1 grain on the first day, 2 on the second, 4 on the third, doubling every day. After a month, the palace granary is empty.

And at a college fest, 10 friends each shake hands with every other friend once. How many handshakes is that?

Both are counting questions: adding up a pattern, and counting choices. Later, “how many steps does this program take?” and “how many ways can this happen?” will turn into exactly these sums.

2 · Predict First

🤔

Rice: 1 grain on day 1, doubling every day (2, 4, 8, …). How many grains in total after 10 days? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

1023 grains. 1 + 2 + 4 + … + 512 = 1023 = 2^10^ − 1. The total is always one less than the next day’s amount: doubling sums stay just under the next power of 2.

Sum notation

Σ (capital sigma) means “add up”. “Σ i for i = 1 to n” means 1 + 2 + … + n: let i take each whole value from 1 to n and add the terms.

1 + 2 + … + n = n(n + 1)/2

Write the sum forwards and backwards and add the two rows column by column: every column adds up to n + 1, and there are n columns. That is twice the sum, so the sum is n(n + 1)/2. For n = 100: 5050.

Useful forms:

• 1 + 2 + … + (n − 1) = n(n − 1)/2
• a + (a + 1) + … + b = (number of terms) × (first + last)/2 = (b − a + 1)(a + b)/2
• 1² + 2² + … + n² = n(n + 1)(2n + 1)/6 (for n = 10: 385)

Doubling sums

1 + 2 + 4 + … + 2^n^ = 2^n+1^ − 1. Reason: add 1 to the sum; 1 + 1 = 2, 2 + 2 = 4, … the whole thing collapses to 2^n+1^.

General ratio r (r ≠ 1): 1 + r + r² + … + r^n^ = (r^n+1^ − 1)/(r − 1). For r = 3, n = 4: (243 − 1)/2 = 121.

Halving sums: n + n/2 + n/4 + … never reaches 2n. For n = 64: 64 + 32 + … + 1 = 127.

Counting: add or multiply

• Sum rule: if a choice is either one of a ways or one of b other ways, there are a + b ways.
• Product rule: if you make one choice in a ways and then another in b ways, there are a × b ways. 3 shirts and 4 trousers give 12 outfits.

Arrangements and choices

• Factorial: n! = n × (n − 1) × … × 1, with 0! = 1. It counts the orders of n different things: the 4 letters of GATE can be arranged in 4! = 24 ways.
• Ordered choices (permutations) of k from n: n!/(n − k)!. Gold, silver, bronze among 5 runners: 5 × 4 × 3 = 60.
• Unordered choices (combinations) of k from n: nCr = n!/(k!(n − k)!). Picking 3 of 7 books: 35.
• Pairs: nC2 = n(n − 1)/2. The 10 friends make 45 handshakes.
• Subsets: each of n items is in or out, so there are 2^n^ subsets.

Counting steps in a pattern

“For each i from 1 to n, do i steps” costs 1 + 2 + … + n = n(n + 1)/2 steps. With n = 20 that is 210. This exact count will come back when programs repeat work.

4 · Visual

Gauss's trick for 1 + 2 + 3 + 4 + 5:

   1 + 2 + 3 + 4 + 5
 + 5 + 4 + 3 + 2 + 1
 -------------------
   6 + 6 + 6 + 6 + 6   = 5 columns x 6 = 30 = twice the sum  ->  sum = 15 = 5(5+1)/2

Staircase picture (each row i has i blocks; the staircase is half of a 5 x 6 rectangle):

 #
 # #
 # # #
 # # # #
 # # # # #

Doubling sum:  1 + 2 + 4 + 8 = 15 = 16 - 1      (always the next power of 2, minus 1)

Pairing the sum with itself and the staircase both show n(n + 1)/2.

Rice per day for 10 days. Total = 1023 = 2¹⁰ − 1: always one grain short of the next day.

5 · Worked Examples

Example 1 Easy

Find 1 + 2 + … + 100 and 10 + 11 + … + 50.

Solution

100 × 101 / 2 = 5050. From 10 to 50 there are 41 terms with average (10 + 50)/2 = 30: 41 × 30 = 1230.

Example 2 Medium

Find 1 + 2 + 4 + … + 512 and 1 + 3 + 9 + 27 + 81.

Solution

512 = 2^9^, so the sum is 2^10^ − 1 = 1023. For ratio 3: (3^5^ − 1)/(3 − 1) = 242/2 = 121.

Example 3 GATE

Count: (a) handshakes among 10 people; (b) arrangements of the letters G, A, T, E; (c) ways to choose 3 books from 7; (d) total steps when, for each i from 1 to 20, you do i steps.

Solution

(a) 10C2 = 10 × 9/2 = 45. (b) 4! = 24. (c) 7C3 = 7 × 6 × 5/(3 × 2 × 1) = 35. (d) 1 + 2 + … + 20 = 20 × 21/2 = 210.

6 · GATE Traps

⚠️

• 1 + 2 + … + (n − 1) is n(n − 1)/2, not n(n + 1)/2: check the last term.
• 2⁰ + 2¹ + … + 2ⁿ has n + 1 terms and sums to 2^n+1^ − 1, not 2^n^ − 1.
• Order matters → permutation; order does not matter → combination. A committee is a combination; a ranking is a permutation.
• 0! = 1, so nC0 = nCn = 1.
• Number of terms from a to b is b − a + 1, not b − a.

8 · Memory Hook

🧠

“Pair it up, double it up.” Pair the first and last terms for 1 + … + n; add one more grain to a doubling pile and it collapses into the next power of 2.

9 · Connect the Dots

Lesson 0.2.1 counted halvings and doublings; this lesson added them up and counted arrangements and choices. Phase 0 is complete: you can read a simple C program, picture memory, and do the arithmetic later lessons need. Next comes Phase 1, starting with the question: besides whole numbers, what other kinds of values can a variable hold, and how much memory does each take?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markSeries

What is 1 + 2 + … + 50?

Numerical answer: ________

Q2NAT1 markDoubling sum

What is 2⁰ + 2¹ + … + 2⁷?

Numerical answer: ________

Q3MCQ1 markFormula

1 + 2 + … + (n − 1) equals:

• (A) n(n − 1)/2
• (B) n(n + 1)/2
• (C) n²/2
• (D) (n − 1)²/2

Q4NAT2 marksCounting

In how many ways can 2 class representatives (equal roles) be chosen from 6 students?

Numerical answer: ________

Q5MSQ2 marksCounting

Which are correct?

• (A) The 5 letters of LINUX can be arranged in 120 ways.
• (B) 1 + 3 + 9 + 27 = 40.
• (C) A set of 5 items has 32 subsets.
• (D) Gold, silver and bronze among 5 runners: 10 ways.

11 · Rule Card

• Σ i (i = 1 to n) = n(n + 1)/2; 1 + … + (n − 1) = n(n − 1)/2.
• a + … + b = (b − a + 1)(a + b)/2.
• Σ i² = n(n + 1)(2n + 1)/6.
• 1 + 2 + … + 2^n^ = 2^n+1^ − 1; 1 + r + … + r^n^ = (r^n+1^ − 1)/(r − 1).
• n + n/2 + n/4 + … < 2n.
• Sum rule (or) add; product rule (and then) multiply.
• n! orders; ordered k of n: n!/(n − k)!; unordered: nCr = n!/(k!(n − k)!); pairs nC2; subsets 2^n^.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

Σ notationarithmetic series n(n+1)/2geometric seriessum ruleproduct rulefactorial n!permutationcombination nCrsubsets 2ⁿ

13 · Answer Vault