Questions on summing series and the method of differences

Question 1

Write down the standard results for the sum of the first n positive integers and the sum of their squares.

Accepted Answer

Σr = n(n + 1)/2 and Σr² = n(n + 1)(2n + 1)/6, both from r = 1 to n. B1 B1 for the two standard results.

Question 2

Using the standard results, show that Σ 4r³ from 1 to n equals n²(n + 1)², and check the formula at n = 3.

Accepted Answer

Σr³ = n²(n + 1)²/4, so multiplying by 4 clears the fraction: Σ4r³ = n²(n + 1)². At n = 3: 4(1 + 8 + 27) = 144 and 9 × 16 = 144. Agreed. M1 for quoting Σr³ = n²(n + 1)²/4, A1 for the printed result, B1 for the check at n = 3.

Question 3

Show that Σ (2r − 1) from 1 to n equals n², and verify the formula at n = 5.

Accepted Answer

Σ(2r − 1) = 2Σr − Σ1 = 2 × n(n + 1)/2 − n = n(n + 1) − n = n². At n = 5: 1 + 3 + 5 + 7 + 9 = 25 = 5². M1 for splitting into 2Σr − n, A1 for n², B1 for the check at n = 5. This is the standard result behind the fact that the first n odd numbers always sum to a perfect square.

Question 4

Using the standard result for Σr², evaluate Σ (3r² + 1) from 1 to 4.

Accepted Answer

Σ(3r² + 1) = 3Σr² + Σ1 = 3 × 4 × 5 × 9/6 + 4 = 90 + 4 = 94. M1 for splitting into 3Σr² + n, A1 for Σr² = 30 at n = 4, A1 for 94. Check directly: 4 + 13 + 28 + 49 = 94. Every constant term in the sum contributes n once, not Σr or Σr².

Question 5

Show that Σ r(r + 2) from 1 to n equals n(n + 1)(2n + 7)/6.

Accepted Answer

Split: Σr² + 2Σr = n(n + 1)(2n + 1)/6 + n(n + 1). Take out n(n + 1)/6: the bracket is (2n + 1) + 6 = 2n + 7, giving n(n + 1)(2n + 7)/6. Check at n = 3: 3 + 8 + 15 = 26, and 3 × 4 × 13/6 = 26. M1 for splitting into Σr² + 2Σr, A1 for both standard results, M1 for taking out n(n + 1)/6, A1 for the printed result.

Question 6

Given that 1/((2r − 1)(2r + 1)) = ½(1/(2r − 1) − 1/(2r + 1)), find Σ 1/((2r − 1)(2r + 1)) from 1 to n.

Accepted Answer

The telescope cancels every inner term: the sum is ½(1 − 1/(2n + 1)) = n/(2n + 1). Check at n = 3: 1/3 + 1/15 + 1/35 = 3/7, and n/(2n + 1) = 3/7. M1 for writing out enough terms, A1 for the surviving pair, A1 for ½(1 − 1/(2n + 1)), A1 for n/(2n + 1).

Question 7

Find Σ r² for r from n + 1 to 2n, simplifying your answer, and verify it at n = 2.

Accepted Answer

Subtract two full sums: Σ to 2n minus Σ to n = 2n(2n + 1)(4n + 1)/6 − n(n + 1)(2n + 1)/6 = n(2n + 1)(7n + 1)/6, after taking out n(2n + 1)/6. At n = 2: 9 + 16 = 25 and 2 × 5 × 15/6 = 25. M1 for the difference of two sums, A1 for both standard results, M1 for taking out n(2n + 1)/6, A1 for n(2n + 1)(7n + 1)/6.

Question 8

A comparison sort works through a list of n items by comparing the first item with each of the other n − 1, the second with each of the n − 2 beyond it, and so on until the last pair. Show that the total number of comparisons is ½n² − ½n, state the order of the algorithm, and find, roughly, the factor by which the number of comparisons rises when the list doubles in length.

Accepted Answer

The comparisons total (n − 1) + (n − 2) + … + 1, which is Σr from 1 to n − 1. The standard result with n − 1 in place of n gives (n − 1)n/2, which expands to ½n² − ½n. The order is read off the dominant term ½n², dropping the constant factor with the lower power: the algorithm is O(n²). Doubling n multiplies that dominant term by 4, so the work roughly quadruples: a list of 100 costs 4,950 comparisons and a list of 200 costs 19,900, a factor of 4.02. M1 for recognising Σr up to n − 1, A1 for ½n² − ½n, B1 for O(n²) via the dominant term, B1 for the factor of about 4.

Question 9

Show that Σ r(r + 1)(r + 2) from 1 to n equals n(n + 1)(n + 2)(n + 3)/4, and verify the formula at n = 3.

Accepted Answer

Expand the term first: r(r + 1)(r + 2) = r³ + 3r² + 2r, so the sum is Σr³ + 3Σr² + 2Σr = n²(n + 1)²/4 + n(n + 1)(2n + 1)/2 + n(n + 1). Take out n(n + 1)/4: the bracket is n(n + 1) + 2(2n + 1) + 4 = n² + 5n + 6 = (n + 2)(n + 3), giving n(n + 1)(n + 2)(n + 3)/4. At n = 3: 6 + 24 + 60 = 90, and 3 × 4 × 5 × 6/4 = 90. Agreed. M1 for expanding to r³ + 3r² + 2r, A1 for all three standard results substituted, M1 for taking out n(n + 1)/4, A1 for factorising the bracket to (n + 2)(n + 3) and the printed result, B1 for the check at n = 3. Factorising early is what keeps this clean; expanding the whole quartic and refactorising it costs minutes.

Question 10

A routing algorithm processes a network of n switches. On its r-th pass (r = 1, 2, …, n) it tests 2r + 1 connections. Show that the total number of connections tested is n² + 2n, state the order of the algorithm, and find, roughly, the factor by which the number of connections tested rises when n doubles.

Accepted Answer

The total is Σ(2r + 1) from 1 to n = 2Σr + n = 2 × n(n + 1)/2 + n = n(n + 1) + n = n² + 2n. M1 for splitting into 2Σr + n, A1 for n² + 2n. The order is read off the dominant term n², dropping the lower power: the algorithm is O(n²). B1 for O(n²) via the dominant term. Doubling n multiplies the dominant term by 4, so the count roughly quadruples: at n = 100 it is 10,200, and at n = 200 it is 40,400, a factor of 3.96. B1 for the factor of about 4. The factor 2 on r and the extra 1 in each term, absent from the plain comparison count earlier in this lesson, do not change the order: a constant factor is dropped, and the 1 adds only n.

Question 11

Show that Σ r²(r + 1) from 1 to n equals n(n + 1)(n + 2)(3n + 1)/12, and verify the formula at n = 3.

Accepted Answer

Expand the term: r²(r + 1) = r³ + r², so the sum is Σr³ + Σr² = n²(n + 1)²/4 + n(n + 1)(2n + 1)/6. Take out n(n + 1)/12: the bracket is 3n(n + 1) + 2(2n + 1) = 3n² + 7n + 2, which factorises as (3n + 1)(n + 2), giving n(n + 1)(n + 2)(3n + 1)/12. At n = 3: 2 + 12 + 36 = 50, and 3 × 4 × 5 × 10/12 = 50. Agreed. M1 for expanding to r³ + r², A1 for both standard results substituted, M1 for taking out n(n + 1)/12, A1 for factorising the bracket to (3n + 1)(n + 2) and the printed result, B1 for the check at n = 3.

Question 12

Express 1/(r(r + 2)) in partial fractions. Hence show that Σ 1/(r(r + 2)) from r = 1 to n is 3/4 − (2n + 3)/(2(n + 1)(n + 2)), and state the sum to infinity.

Accepted Answer

1/(r(r + 2)) = A/r + B/(r + 2) gives 1 = A(r + 2) + Br. Putting r = 0 gives A = ½ and r = −2 gives B = −½, so 1/(r(r + 2)) = ½(1/r − 1/(r + 2)).
Now write the terms out. Each negative part cancels the positive part two rows below, not one, so two terms survive at each end rather than one:
2Σ = (1/1 − 1/3) + (1/2 − 1/4) + (1/3 − 1/5) + … + (1/(n − 1) − 1/(n + 1)) + (1/n − 1/(n + 2)).
The survivors are 1 and 1/2 at the top and −1/(n + 1) and −1/(n + 2) at the bottom.
So Σ = ½[3/2 − 1/(n + 1) − 1/(n + 2)]. Combining the last two over a common denominator: 1/(n + 1) + 1/(n + 2) = (2n + 3)/((n + 1)(n + 2)).
Hence Σ = 3/4 − (2n + 3)/(2(n + 1)(n + 2)), as required. Check at n = 2: 3/4 − 7/24 = 11/24, and 1/3 + 1/8 = 11/24.
As n → ∞ the subtracted fraction tends to 0, so the sum to infinity is 3/4.
M1 for setting up the partial fractions, A1 for the printed pair, M1 for writing out enough terms, A1 for the four survivors, A1 for ½[3/2 − 1/(n + 1) − 1/(n + 2)], A1 for the printed result, B1 for the sum to infinity. Assuming one survivor at each end, as in the gap-one case, gives 1/2 in place of 3/4.

Question 13

Show that 1/(r(r + 1)) − 1/((r + 1)(r + 2)) = 2/(r(r + 1)(r + 2)). Hence show that Σ 1/(r(r + 1)(r + 2)) from r = 1 to n equals 1/4 − 1/(2(n + 1)(n + 2)), state the sum to infinity, and find the least n for which the sum is within 1/100 of it.

Accepted Answer

Over a common denominator the left side is ((r + 2) − r)/(r(r + 1)(r + 2)) = 2/(r(r + 1)(r + 2)), as required. So each term is ½[f(r) − f(r + 1)] with f(r) = 1/(r(r + 1)), and the sum telescopes:
2Σ = (1/(1 × 2) − 1/(2 × 3)) + (1/(2 × 3) − 1/(3 × 4)) + … + (1/(n(n + 1)) − 1/((n + 1)(n + 2))).
Every inner value appears once with each sign, so only 1/2 and −1/((n + 1)(n + 2)) survive, and Σ = 1/4 − 1/(2(n + 1)(n + 2)). Check at n = 2: 1/6 + 1/24 = 5/24, and 1/4 − 1/24 = 5/24.
As n → ∞ the subtracted fraction tends to 0, so the sum to infinity is 1/4. The gap is 1/(2(n + 1)(n + 2)) < 1/100 when (n + 1)(n + 2) > 50: at n = 5 the product is 42, at n = 6 it is 56, so the least n is 6. M1 for combining over a common denominator, A1 for the printed identity, M1 for writing out both ends of the telescope, A1 for 1/4 − 1/(2(n + 1)(n + 2)), B1 for 1/4, M1 for the inequality (n + 1)(n + 2) > 50, A1 for n = 6. This is a gap-one telescope in f(r) = 1/(r(r + 1)), so one survivor at each end, even though three factors sit in the denominator.

Question 14

Prove that r³ − (r − 1)³ = 3r² − 3r + 1. Hence, using the method of differences, derive the standard result Σr² = n(n + 1)(2n + 1)/6.

Accepted Answer

Expanding, (r − 1)³ = r³ − 3r² + 3r − 1, so r³ − (r − 1)³ = r³ − (r³ − 3r² + 3r − 1) = 3r² − 3r + 1, as required. M1 for expanding (r − 1)³, A1 for the identity. Summing both sides from r = 1 to n, the left side telescopes: each middle cube appears once with each sign, leaving Σ[r³ − (r − 1)³] = n³ − 0³ = n³. So 3Σr² − 3Σr + n = n³. Rearranging, 3Σr² = n³ + 3Σr − n = n³ + 3 × n(n + 1)/2 − n. Combining over a common denominator of 6: 6Σr² = 2n³ + 3n(n + 1) − 2n = 2n³ + 3n² + n = n(2n² + 3n + 1) = n(2n + 1)(n + 1), so Σr² = n(n + 1)(2n + 1)/6, the standard result. M1 for writing out the telescope, A1 for the sum collapsing to n³, M1 for substituting Σr = n(n + 1)/2 and rearranging, A1 for reaching a common denominator of 6 and factorising to the printed result. This proves the standard result rather than quoting it, using the method of differences on cubes instead of on a fraction.

Question 15

An algorithm's number of operations is modelled by T(n) = Σr² for r from 1 to n. Show that T(n) can be written as n³/3 + n²/2 + n/6, state the order of the algorithm using the dominant term, and find, roughly, the factor by which the number of operations rises when n doubles.

Accepted Answer

T(n) = n(n + 1)(2n + 1)/6. Expanding the numerator, n(n + 1)(2n + 1) = 2n³ + 3n² + n. M1 for expanding the numerator. So T(n) = (2n³ + 3n² + n)/6 = n³/3 + n²/2 + n/6. A1 for splitting the fraction into the printed three terms. The dominant term is n³/3, since it outgrows n²/2 and n/6 as n rises, so the algorithm is O(n³), cubic order rather than the quadratic order of the earlier counting questions in this lesson. B1 for identifying n³/3 as dominant, B1 for O(n³) stated. Doubling n multiplies the dominant term by 2³ = 8: at n = 100, T(100) = 338,350, and at n = 200, T(200) = 2,686,700. M1 for evaluating T(n) at n = 100 and n = 200 (or arguing from 2³ directly). The ratio 2,686,700/338,350 = 7.94, close to 8. A1 for the factor of about 8.