The question of this worksheet: How do you quickly compute a sum with very many terms, and how can you be sure that the formula you found is true for every $n$?
Start from what you know
Three quick checks. If one of them gives you trouble, write it down: that is the one you go back to first.
-
Calculate $1+2+3+\ldots+100$. Hint: add the first term to the last one, the second to the one before the last, …
-
Write the next two terms:
a) $1; 4; 9; 16; \ldots$
b) $2; 5; 8; 11; \ldots$
-
Expand: $(k+1)^2$ and $(k+1)^3$.
Short theory
1. The Σ (sigma) symbol
Definition · Writing a sum in short form
The sum $a_1+a_2+a_3+\ldots+a_n$ is written in short form as:
$$\sum_{k=1}^{n}{a_k}=a_1+a_2+\ldots+a_n$$
and is read “the sum from $k$ equals 1 to $n$ of $a_k$”.
- $k$ is the summation index: it takes the values $1; 2; \ldots; n$ in turn. The letter does not matter: $\sum_{k=1}^{n}{a_k}=\sum_{i=1}^{n}{a_i}$.
- 1 is the lower limit and $n$ is the upper limit of the sum.
- $a_k$ is the general term of the sum: the rule that gives each term.
- The sum $\sum_{k=m}^{n}{a_k}$ has $n-m+1$ terms.
Examples · Writing the sum out
$\sum_{k=1}^{4}{k^2}=1^2+2^2+3^2+4^2=1+4+9+16=30$
$\sum_{k=3}^{6}{(2k+1)}=7+9+11+13=40$ (it has $6-3+1=4$ terms)
$\sum_{k=1}^{5}{3}=3+3+3+3+3=15$ (the general term does not depend on $k$)
2. Writing a sum with Σ: finding the general term
Method
Step 1. Number the terms: the first one has $k=1$, the second $k=2$, …
Step 2. Notice what changes from one term to the next and what stays the same.
Step 3. Write the general term $a_k$ as an expression in $k$.
Step 4. Find the upper limit from the last term: solve the equation $a_k=$ the last term.
Step 5. Check the formula on the first and on the last term.
Example 1 · Finding the general term
a) $1+3+5+\ldots+(2n-1)$: the odd numbers, $a_k=2k-1$. For $k=1$ you get 1, for $k=n$ you get $2n-1$. So the sum is $\sum_{k=1}^{n}{(2k-1)}$.
b) $1\cdot 2+2\cdot 3+3\cdot 4+\ldots+n(n+1)$: each term is the product of two consecutive numbers, $a_k=k(k+1)$. The sum is $\sum_{k=1}^{n}{k(k+1)}$.
c) $2+5+8+\ldots+152$: the terms always grow by 3, so $a_k=3k+c$. From $a_1=2$ you get $c=-1$, that is $a_k=3k-1$. From $3k-1=152$ you get $k=51$. The sum is $\sum_{k=1}^{51}{(3k-1)}$.
How to recognise it
The terms always grow by the same number $d$ → $a_k=d\cdot k+c$. Squares, cubes → $k^2$, $k^3$. Alternating signs $+, -, +, \ldots$ → the factor $\left(-1\right)^{k+1}$.
3. Properties of sums
Properties · Remember
(P1) A constant factor comes out in front of the sum. If $c$ does not depend on $k$:
$$\sum_{k=1}^{n}{c\cdot a_k}=c\cdot \sum_{k=1}^{n}{a_k}$$
(P2) The sum of a sum (difference) “splits” into two sums.
$$\sum_{k=1}^{n}{(a_k\pm b_k)}=\sum_{k=1}^{n}{a_k}\pm \sum_{k=1}^{n}{b_k}$$
Linearity combines (P1) and (P2): for any numbers $\alpha$ and $\beta$ that do not depend on $k$,
$$\sum_{k=1}^{n}{(\alpha \cdot a_k+\beta \cdot b_k)}=\alpha \cdot \sum_{k=1}^{n}{a_k}+\beta \cdot \sum_{k=1}^{n}{b_k}$$
(P3) A sum can be split into two pieces. For $1\le m<n$:
$$\sum_{k=m+1}^{n}{a_k}=\sum_{k=1}^{n}{a_k}-\sum_{k=1}^{m}{a_k}$$
Watch out · Common mistakes
- $\sum_{k=1}^{n}{c}=c+c+\ldots+c=n\cdot c$, not $c$: the constant appears $n$ times.
- A product does not split: $\sum_{k=1}^{n}{a_k\cdot b_k}\ne \sum_{k=1}^{n}{a_k}\cdot \sum_{k=1}^{n}{b_k}$. For $n=2$ and $a_k=b_k=k$: $1+4=5$, but $3\cdot 3=9$.
- Only what does not depend on $k$ comes out in front of the sum: $\sum_{k=1}^{n}{k\cdot k}\ne k\cdot \sum_{k=1}^{n}{k}$.
4. Standard sums
The four formulas below are used in almost every calculation with sums. Learn them by heart.
Standard sums
(S1) The sum of a constant
$$\sum_{k=1}^{n}{c}=n\cdot c$$
Example: $\sum_{k=1}^{10}{7}=70$
(S2) The sum of the first n nonzero natural numbers
$$\sum_{k=1}^{n}{k}=\frac{n(n+1)}{2}$$
Example: $1+2+\ldots+100=5050$
(S3) The sum of the squares
$$\sum_{k=1}^{n}{k^2}=\frac{n(n+1)(2n+1)}{6}$$
Example: $1^2+2^2+\ldots+10^2=385$
(S4) The sum of the cubes
$$\sum_{k=1}^{n}{k^3}=\left(\frac{n(n+1)}{2}\right)^2$$
Example: $1^3+2^3+3^3+4^3=100=10^2$
Method · Computing a sum
Step 1. Write the sum with Σ (find the general term).
Step 2. Expand the general term into a sum of powers of $k$: $k^3$, $k^2$, $k$, constants.
Step 3. Split the sum (P2) and take the constants out in front (P1).
Step 4. Apply the standard sums (S1)–(S4) and bring the result to its simplest form.
Step 5. Check the formula for $n=1$ and $n=2$.
Example 2 · Step by step
a) $1+3+5+\ldots+(2n-1)=\sum_{k=1}^{n}{(2k-1)}=2\cdot \sum_{k=1}^{n}{k}-\sum_{k=1}^{n}{1}=2\cdot \frac{n(n+1)}{2}-n=n^2$.
b) $S_n=1\cdot 2+2\cdot 3+\ldots+n(n+1)$.
Step 1. $S_n=\sum_{k=1}^{n}{k(k+1)}=\sum_{k=1}^{n}{(k^2+k)}$
Step 2. $S_n=\sum_{k=1}^{n}{k^2}+\sum_{k=1}^{n}{k}=\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}$
Step 3. Take out the common factor $\frac{n(n+1)}{6}$: $S_n=\frac{n(n+1)}{6}\cdot (2n+1+3)=\frac{n(n+1)(n+2)}{3}$.
Check: $n=1$: $1\cdot 2=2$ and $\frac{1\cdot 2\cdot 3}{3}=2$ ✓; $n=2$: $2+6=8$ and $\frac{2\cdot 3\cdot 4}{3}=8$ ✓.
c) With (P3): $11^2+12^2+\ldots+20^2=\sum_{k=1}^{20}{k^2}-\sum_{k=1}^{10}{k^2}=2870-385=2485$.
5. The method of mathematical induction
Explore · Are a few checks enough?
In Example 2 b) we checked the formula for $n=1$ and $n=2$. We could also check it for $n=3$, $n=4$, …, $n=100$.
Would that be a proof for every $n$? How could you be sure without checking forever?
The principle of mathematical induction
Let $P(n)$ be a statement that depends on the natural number $n\ge n_0$. If:
Step I (the check). $P(n_0)$ is true;
Step II (the proof). for every $k\ge n_0$, if $P(k)$ is true then $P(k+1)$ is true, that is $P(k)\Rightarrow P(k+1)$,
then $P(n)$ is true for every $n\ge n_0$.
The picture: a row of dominoes. The first domino falls (step I) and each domino knocks over the next one (step II). Then all the dominoes fall.
How to write it
“Let $P(n)$: …, $n\ge n_0$.
Step I. $P(n_0)$: … (I compute the two sides separately) …, so $P(n_0)$ is true.
Step II. Assume $P(k)$ is true (the induction hypothesis) and prove $P(k+1)$. Start from the left side of $P(k+1)$, use the induction hypothesis and reach the right side.
By the principle of mathematical induction, $P(n)$ is true for every $n\ge n_0$.”
Example 3 · Proving the formula of Example 2 b) by induction
$P(n)$: $1\cdot 2+2\cdot 3+\ldots+n(n+1)=\frac{n(n+1)(n+2)}{3}$, $n\ge 1$.
Step I. $P(1)$: the left side is $1\cdot 2=2$, the right side is $\frac{1\cdot 2\cdot 3}{3}=2$. So $P(1)$ is true.
Step II. Assume $P(k)$: $1\cdot 2+\ldots+k(k+1)=\frac{k(k+1)(k+2)}{3}$. Prove $P(k+1)$: $1\cdot 2+\ldots+k(k+1)+(k+1)(k+2)=\frac{(k+1)(k+2)(k+3)}{3}$.
Left side $=\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=(k+1)(k+2)\cdot \left(\frac{k}{3}+1\right)=\frac{(k+1)(k+2)(k+3)}{3}$, which is the right side.
Conclusion. By the principle of mathematical induction, $P(n)$ is true for every $n\ge 1$.
Watch out · Both steps are required
Let $P(n)$: $1+2+\ldots+n=\frac{n^2+n+2}{2}$. Step II works: if $P(k)$ were true, then $\frac{k^2+k+2}{2}+(k+1)=\frac{(k+1)^2+(k+1)+2}{2}$. But $P(1)$ is false ($1\ne 2$), and the formula is false for every $n$. Without step I, the “proof” proves nothing.
The other way round: checks for $n=1, 2, 3, \ldots$ do not replace step II. Examples do not prove.
The logical thread: from a sum to a proved formula
★ Most important
This is the core of solving these problems. Follow these steps, in this order, every time you work with sums.
- I write the sum with Σ
- I expand the general term
- I apply (P1), (P2) and (S1)–(S4)
- I check for n = 1 and n = 2
- I prove it by induction
Problems on three levels
For each problem, write the steps, not just the result: which property or which standard sum you use. Proofs by induction are written in full, with both steps.
Basic level
-
Write out, then calculate:
a) $\sum_{k=1}^{5}{k}$;
b) $\sum_{k=1}^{4}{(2k+3)}$;
c) $\sum_{k=2}^{5}{k^2}$;
d) $\sum_{k=1}^{6}{4}$;
e) $\sum_{k=1}^{4}{\left(-1\right)^k\cdot k}$.
-
How many terms does each sum have?
a) $\sum_{k=1}^{20}{a_k}$;
b) $\sum_{k=5}^{30}{a_k}$;
c) $\sum_{k=0}^{n}{a_k}$.
-
Write with the Σ symbol, after you find the general term:
a) $2+4+6+\ldots+40$;
b) $1+4+9+\ldots+100$;
c) $3+7+11+\ldots+(4n-1)$;
d) $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots+\frac{1}{n(n+1)}$.
-
Calculate, using the standard sums:
a) $1+2+\ldots+50$;
b) $1^2+2^2+\ldots+12^2$;
c) $1^3+2^3+\ldots+6^3$;
d) $\sum_{k=1}^{15}{3}$.
-
Calculate, using the properties of sums:
a) $\sum_{k=1}^{20}{(3k+2)}$;
b) $\sum_{k=1}^{10}{(k^2-k)}$;
c) $\sum_{k=1}^{n}{(4k-1)}$.
-
Prove by mathematical induction that, for every $n\in \N^*$:
a) $1+2+\ldots+n=\frac{n(n+1)}{2}$;
b) $1+3+5+\ldots+(2n-1)=n^2$.
Consolidated level
-
Write with Σ, then calculate:
a) $1+5+9+\ldots+(4n-3)$;
b) $1\cdot 4+2\cdot 5+\ldots+n(n+3)$;
c) $1^2+3^2+5^2+\ldots+(2n-1)^2$.
-
Let $S_n=1\cdot 3+2\cdot 4+3\cdot 5+\ldots+n(n+2)$.
a) Calculate $S_n$, using the properties and the standard sums.
b) Prove by induction the formula you found in a).
-
Calculate, using property (P3):
a) $\sum_{k=21}^{40}{k}$;
b) $\sum_{k=6}^{15}{k^2}$;
c) $\sum_{k=n+1}^{2n}{k}$.
-
Prove by mathematical induction that, for every $n\in \N^*$:
a) $1^2+2^2+\ldots+n^2=\frac{n(n+1)(2n+1)}{6}$;
b) $1^3+2^3+\ldots+n^3=\left(\frac{n(n+1)}{2}\right)^2$.
-
Find the nonzero natural number $n$ for which:
a) $1+2+\ldots+n=210$;
b) $1^3+2^3+\ldots+n^3=3025$.
Advanced level
-
A telescoping sum.
a) Check the equality $\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$.
b) Calculate $\sum_{k=1}^{n}{\frac{1}{k(k+1)}}$. Hint: write it out and watch what cancels.
c) Prove the result of b) by induction.
-
Let $T_n=\sum_{k=1}^{n}{k(k+1)(k+2)}$.
a) Calculate $T_n$ and write the result as a product of factors.
b) Prove the formula you found by induction.
c) Compare it with $\sum_{k=1}^{n}{k}=\frac{n(n+1)}{2}$ and with $\sum_{k=1}^{n}{k(k+1)}=\frac{n(n+1)(n+2)}{3}$. What rule do you notice? What formula do you suggest for $\sum_{k=1}^{n}{k(k+1)(k+2)(k+3)}$?
-
Prove by induction that $1+2\cdot 2+3\cdot 2^2+\ldots+n\cdot 2^{n-1}=(n-1)\cdot 2^n+1$, for every $n\in \N^*$.
-
Find the mistake. A student writes: “Let $P(n)$: $2+4+\ldots+2n=n^2+n+1$. I assume $P(k)$. Then $2+4+\ldots+2k+2(k+1)=k^2+k+1+2k+2=(k+1)^2+(k+1)+1$, so $P(k+1)$ is true. Therefore the formula is true for every $n$.”
a) Check the formula for $n=1$.
b) Which step is missing?
c) What is the correct formula? Prove it.
-
Challenge. Prove by induction that, for every $n\in \N^*$:
$$1+\frac{1}{2^2}+\frac{1}{3^2}+\ldots+\frac{1}{n^2}\le 2-\frac{1}{n}$$
What can you say about the sum $1+\frac{1}{2^2}+\ldots+\frac{1}{100^2}$?