Use the patterns given below to prove the following WITHOUT using mathematical induction. (A) Observe the pattern: 1 = 1 1 + 3 = 4 1 + 3 + 5 = 9 1 + 3 + 5 + 7 = 16 ... Use this to prove that sum_{k=1}^{n} (2k - 1) = n^2. (B) Use the result of (A) to prove that: sum_{k=1}^{n} k = n(n+1)/2.

GATE 1994 · Discrete Mathematics · Summation · medium

Answer: Part (A): sum_{k=1}^{n}(2k-1) = n^2 (by telescoping). Part (B): sum_{k=1}^{n} k = n(n+1)/2 (by splitting the odd sum).

1. Key algebraic identity: Expand: k^2 - (k^2 - 2k + 1) = 2k - 1. This holds for every integer k >= 1.
2. Prove part (A): telescoping sum: The right-hand side telescopes: (1^2 - 0^2) + (2^2 - 1^2) + ... + (n^2 - (n-1)^2) = n^2 - 0 = n^2.
3. Split the odd-number sum to involve 1+2+...+n: Linearity: sum(2k-1) = 2*sum(k) - sum(1) = 2S - n. From part (A) this equals n^2.
4. Conclude part (B): From 2S = n(n+1), divide both sides by 2: S = n(n+1)/2.