Questions on proof by induction: sums and series

Question 1

State the two things a proof by induction must establish, and explain briefly why together they prove a statement for every positive integer n.

Accepted Answer

A base case (the statement holds at n = 1) and an inductive step (truth at n = k forces truth at n = k + 1). The base case starts the chain and the step passes truth along it, so every positive integer is eventually reached. B1 B1 for the base case and the inductive step.

Question 2

For the claim 1 + 3 + 5 + … + (2n − 1) = n², verify the base case and write down the inductive hypothesis.

Accepted Answer

At n = 1 the left side is 1 and the right side is 1² = 1, so the base case holds. Hypothesis: assume 1 + 3 + … + (2k − 1) = k² for some positive integer k. B1 for the base case, B1 for the hypothesis.

Question 3

A student verifies that a claim P(n) is true at n = 1, but does not attempt an inductive step. State exactly what has been established, and explain why nothing has been said about n = 2.

Accepted Answer

Only that the claim holds at n = 1: that single case is now known true, and nothing more. B1 for stating what has been established. Nothing links n = 1 to n = 2, because no argument has been given showing that truth at one value forces truth at the next; the inductive step is exactly that link, and without it a true first case says nothing about any later one. B1 for the missing link. A complete proof needs both a base case and an inductive step: a valid step with no true starting value has nothing to carry forward. B1 for both parts being required.

Question 4

For the claim Σr², r = 1 to n, equals n(n + 1)(2n + 1)/6, verify both sides at n = 1 and at n = 2, and explain why checking two cases still falls short of a proof for every positive integer n.

Accepted Answer

At n = 1, the left side is 1² = 1, and the right side is 1 × 2 × 3/6 = 1: equal. At n = 2, the left side is 1² + 2² = 5, and the right side is 2 × 3 × 5/6 = 5: equal too. B1 for both verifications. Checking n = 1 and n = 2 establishes only those two specific cases; nothing has been shown about n = 3, or about any n beyond the two checked, because no argument links one case to the next. B1 for naming that gap. Only an inductive step, which shows truth at an arbitrary k forces truth at k + 1, closes every remaining case at once; a finite list of checks, however long, never does. B1 for identifying what the inductive step supplies that a list of checks does not.

Question 5

Complete the inductive step for 1 + 3 + 5 + … + (2n − 1) = n², and state the conclusion.

Accepted Answer

Assuming the sum to k terms is k², adding the next odd number gives k² + (2k + 1) = (k + 1)². That is the claim at n = k + 1. With the base case established, the statement holds for all positive integers n by induction. M1 for adding the next odd number, A1 for (k + 1)², A1 for the conclusion.

Question 6

Prove by induction that the sum of the first n positive integers is n(n + 1)/2.

Accepted Answer

Base: n = 1 gives 1 = 1 × 2/2. Step: assume the sum to k is k(k + 1)/2; adding k + 1 gives k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, the formula at k + 1. Both parts hold, so the result is true for all n. B1 for the base case, M1 for adding k + 1 to the assumed sum, dM1 for taking out the common factor, A1 for (k + 1)(k + 2)/2, A1 for the conclusion.

Question 7

Prove by induction that 2 + 4 + 8 + … + 2ⁿ = 2ⁿ⁺¹ − 2.

Accepted Answer

Base: n = 1 gives 2 = 2² − 2 = 2. Step: assume the sum to k is 2^k+1 − 2. Adding the next term 2^k+1 gives 2 × 2^k+1 − 2 = 2^k+2 − 2, which is the claim at k + 1. A spot check at n = 4: 2 + 4 + 8 + 16 = 30 = 2⁵ − 2. B1 for the base case, B1 for the hypothesis, M1 for adding 2^k+1, A1 for 2^k+2 − 2, A1 for the conclusion.

Question 8

A student proves the inductive step for a formula but skips the base case. Explain why nothing has been proved, using the false claim 1 + 3 + … + (2n − 1) = n² + 1 as an illustration.

Accepted Answer

The step only passes truth along; without a first true case there is nothing to pass. The false formula n² + 1 also survives the inductive step, since adding 2k + 1 to k² + 1 gives (k + 1)² + 1. Of the two parts, only the base case fails, 1 ≠ 2, which is the step the given argument omits. B1 for the step needing a first true case, M1 for the false formula surviving the step, A1 for its failure at n = 1.

Question 9

Prove by induction that the sum of the squares of the first n positive integers is n(n + 1)(2n + 1)/6.

Accepted Answer

Base: n = 1 gives 1² = 1, and 1 × 2 × 3/6 = 1. B1. Step: assume the sum to k terms is k(k + 1)(2k + 1)/6; adding (k + 1)² gives k(k + 1)(2k + 1)/6 + (k + 1)². M1 for adding (k + 1)². Taking out the common factor (k + 1), this is (k + 1)[k(2k + 1) + 6(k + 1)]/6. dM1 for the common factor. Expanding the bracket, k(2k + 1) + 6(k + 1) = 2k² + 7k + 6, which factorises as (2k + 3)(k + 2). A1 for 2k² + 7k + 6. So the sum is (k + 1)(k + 2)(2k + 3)/6, which is the formula with k + 1 in place of k. A1 for matching the formula at k + 1. Both parts hold, so the result is true for all n by induction. A1 for the conclusion.

Question 10

Prove by induction that Σ(3r − 1), r = 1 to n, equals n(3n + 1)/2.

Accepted Answer

Base: n = 1 gives 3(1) − 1 = 2, and 1 × 4/2 = 2. B1. Step: assume the sum to k terms is k(3k + 1)/2; adding the next term, 3(k + 1) − 1 = 3k + 2, gives k(3k + 1)/2 + (3k + 2) = [k(3k + 1) + 2(3k + 2)]/2 = (3k² + 7k + 4)/2. M1 for adding 3k + 2. This factorises as (k + 1)(3k + 4)/2, which is the formula with k + 1 in place of k. A1 for the factorised form matching. True for n = 1 and inherited from k to k + 1, so true for all positive integers n by induction. A1 for the conclusion.

Question 11

Prove by induction that the sum of the cubes of the first n positive integers is [n(n + 1)/2]².

Accepted Answer

Base: n = 1 gives 1³ = 1, and [1 × 2/2]² = 1. B1. Step: assume the sum to k terms is [k(k + 1)/2]²; adding (k + 1)³ gives [k(k + 1)/2]² + (k + 1)³. M1 for adding (k + 1)³. Taking out the common factor (k + 1)², this is (k + 1)²[k²/4 + (k + 1)] = (k + 1)²(k² + 4k + 4)/4. dM1 for the common factor. Since k² + 4k + 4 = (k + 2)², the sum is [(k + 1)(k + 2)/2]², which is the formula with k + 1 in place of k. A1 for that simplification. True for n = 1 and inherited from k to k + 1, so true for all positive integers n by induction. A1 for the conclusion. The squared closed form is what makes taking out (k + 1)² rather than (k + 1) the useful move here.

Question 12

Prove by induction that the sum of r × 2^r from r = 1 to n equals (n − 1)2ⁿ⁺¹ + 2 for all positive integers n.

Accepted Answer

Base: at n = 1 the sum is 1 × 2 = 2, and the formula gives 0 × 4 + 2 = 2, so the two agree. Step: assume the sum to k terms is (k − 1)2^k+1 + 2. Adding the next term (k + 1)2^k+1 gives (k − 1)2^k+1 + (k + 1)2^k+1 + 2. Take out the common factor 2^k+1, leaving 2^k+1(k − 1 + k + 1) + 2 = 2^k+1(2k) + 2 = k2^k+2 + 2. The formula at n = k + 1 reads ((k + 1) − 1)2^k+2 + 2 = k2^k+2 + 2, which matches. True at n = 1 and inherited at every step, so true for all positive integers n by induction. B1 for the base case, M1 for adding (k + 1)2^k+1, dM1 for taking out 2^k+1, A1 for k2^k+2 + 2, A1 for matching the formula at k + 1, A1 for the conclusion.

Question 13

Let T(n) = 1/(1 × 3) + 1/(3 × 5) + … + 1/((2n − 1)(2n + 1)). Find T(1), T(2) and T(3), conjecture a formula for T(n), and prove it by induction.

Accepted Answer

T(1) = 1/3. T(2) = 1/3 + 1/15 = 5/15 + 1/15 = 6/15 = 2/5. T(3) = 2/5 + 1/35 = 14/35 + 1/35 = 15/35 = 3/7. B1 for the three values. The numerators are 1, 2, 3 against denominators 3, 5, 7, so the conjecture is T(n) = n/(2n + 1). B1 for the conjecture, stated as an equation, which agrees with T(1) = 1/3 above. Step: assume T(k) = k/(2k + 1); adding the next term, 1/((2k + 1)(2k + 3)), gives k/(2k + 1) + 1/((2k + 1)(2k + 3)). M1 for adding the next term. Over the common denominator (2k + 1)(2k + 3), this is [k(2k + 3) + 1]/[(2k + 1)(2k + 3)] = (2k² + 3k + 1)/[(2k + 1)(2k + 3)]. dM1 for the common denominator. The numerator factorises as (2k + 1)(k + 1), so T(k + 1) = (k + 1)/(2k + 3), which is the conjecture with k + 1 in place of k. A1 for that simplification. True at n = 1 and inherited at every step, so T(n) = n/(2n + 1) for all positive integers n by induction. A1 for the conclusion.

Question 14

Prove by induction that the sum of the squares of the first n odd numbers, 1² + 3² + … + (2n − 1)², equals n(2n − 1)(2n + 1)/3 for all positive integers n. Hence find the sum of the squares of the first 10 odd numbers.

Accepted Answer

Base: n = 1 gives 1² = 1, and 1 × 1 × 3/3 = 1. B1. Step: assume the sum to k terms is k(2k − 1)(2k + 1)/3; adding the next odd square, (2k + 1)², gives k(2k − 1)(2k + 1)/3 + (2k + 1)². M1 for adding (2k + 1)². Taking out the common factor (2k + 1), this is (2k + 1)[k(2k − 1) + 3(2k + 1)]/3 = (2k + 1)(2k² + 5k + 3)/3. dM1 for the common factor. Since 2k² + 5k + 3 = (k + 1)(2k + 3), the sum is (k + 1)(2k + 1)(2k + 3)/3, which is the formula with k + 1 in place of k. A1 for that factorisation matching. True at n = 1 and inherited at every step, so the formula holds for all positive integers n by induction. A1 for the conclusion. With n = 10, the sum is 10 × 19 × 21/3 = 10 × 133 = 1330. A1 for 1330.

Question 15

Prove by induction that Σ(r² + r), r = 1 to n, equals n(n + 1)(n + 2)/3.

Accepted Answer

Base: n = 1 gives 1² + 1 = 2, and 1 × 2 × 3/3 = 2. B1. Step: assume the sum to k terms is k(k + 1)(k + 2)/3; adding the next term, (k + 1)² + (k + 1) = (k + 1)(k + 2), gives k(k + 1)(k + 2)/3 + (k + 1)(k + 2). M1 for adding (k + 1)(k + 2). Taking out the common factor (k + 1)(k + 2), this is (k + 1)(k + 2)[k/3 + 1] = (k + 1)(k + 2)(k + 3)/3, which is the formula with k + 1 in place of k. dM1 for the common factor, A1 for matching the formula at k + 1. True for n = 1 and inherited from k to k + 1, so true for all positive integers n by induction. A1 for the conclusion.