Subsection 8.8.7 The Sum of Squares
Let’s prove another summation claim, again using induction.
Prove that, for n ≥ 0,
∑_(i=0)^n▒i^2 = (n (n+1)(2n+1))/6
Exercises Exercises
1.
Consider the claim that the sum of the first n powers of 2 is \(2^{n + 1} - 1\) . This time we want to start n at 0. So we can write the claim as follows:
∀n≥0 (\((\sum_{i = 0}^{n}{2^{i})}\) = \(2^{n + 1} - 1\))
Recall that we read this as, “For any n ≥ 0, the sum, as i goes from 0 to n, of 2i is \(2^{n + 1} - 1\text{.}\) Using … notation, we’re claiming:
20 + 21 + 22 + 23 + … + 2n = \(2^{n + 1} - 1\)
Also recall that 20 = 1.
We first check for plausibility:
(n = 0) 1 = 21 - 1 = 1
(n = 1) 1 + 2 = 22 - 1 = 3
(n = 2) 1 + 2 + 4 = 23 - 1 = 7
(n = 3) 1 + 2 + 4 + 8 = 24 - 1 = 15, and so forth.
Now we’d like to use induction to prove that the claim is true. Do that in three steps:
Write an explicit statement of the predicate, which we’ll call P(n).
(Base Case) Prove that P(n) holds for some base case b.
(Induction Step) Prove that, for all integers n ≥ b, P(n) → P(n+1).
P(n) (∑_(i=0)^n▒〖2^i)〗 = 2^(n+1)-1
Next, do the base case: Prove that P(0) is true. Click here to check what you’ve written before going on. When clicked, should see:
We actually did this above. Evaluating the two sides of the equation:
Left hand side: (∑_(i=0)^0▒2^i ) = 20 = 1
Right hand side: 2^(0+1)-1 = 21 – 1 = 1
Next, do the induction step. To get going, write an explicit statement of what we need to prove. (The instruction given above for step 3 is generic. Write the specific claim that we need to prove for this problem.) Click here to check what you’ve written before going on. When clicked, should see:
We must prove:
n0 ((∑_(i=0)^n▒2^i ) = 2^(n+1)-1) ((∑_(i=0)^(n+1)▒〖2^i)〗 = 2^((n+1)+1)-1)
Just to be totally clear, write the inductive hypothesis. Click here to check what you’ve written before going on. When clicked, should see:
(∑_(i=0)^n▒〖2^i)〗 = 2^(n+1)-1
Now write the proof of the induction step. You can click here for a hint. When clicked, should see:
Write an expression for the sum of the first n+1 powers of 2. Then see if you can find a way to substitute the inductive hypothesis for some subexpression within it. Then see if you can simplify and get the required expression as a result.
If you’re still stuck, click here for another hint. When clicked, should see:
The sum of the first n+1 powers of 2 is the sum of the first n of them, plus the next one. So we have:
(∑_(i=0)^(n+1)▒2^i ) = (∑_(i=0)^n▒2^i ) + 2n+1
Look at this expression and see if you can find a way to use the inductive hypothesis.
Once you’ve finished your proof, click here to see ours: When clicked, should see: We must prove:
n0 ((∑_(i=0)^n▒〖2^i)〗 = 2^(n+1)-1) ((∑_(i=0)^(n+1)▒2^i ) = 2^((n+1)+1)-1)
The proof is by induction on n.
Base case:
(∑_(i=0)^0▒2^i ) = 20 = 1, and
2^(0+1)-1 = 21 – 1 = 1
Inductive step:
\begin{gather*} (∑_(i=0)^(n+1)▒2^i ) = (∑_(i=0)^n▒2^i ) + 2n+1 Definition of the sum for (n+1) \\ = 〖(2〗^(n+1)-1) + 2n+1 By using the inductive hypothesis \\ = 2 (2n+1) – 1 \\ = 2(n+1)+1 – 1 \end{gather*}
By the Principle of Mathematical Induction, we have thus proved our claim:
n0 ((∑_(i=0)^n▒〖2^i)〗 = 2^(n+1)-1)
2.
Consider the claim that the sum of the first n odd positive integers is n2. We first check for plausibility:
(n = 1) 1 = 1 = 12.
(n = 2) 1 + 3 = 4 = 22.
(n = 3) 1 + 3 + 5 = 9 = 32.
(n = 4) 1 + 3 + 5 + 7 = 16 = 42, and so forth.
Let Oddi = 2(i – 1) + 1 denote the ith odd positive integer. (So, for example, the first odd positive integer is 2(1 – 1) + 1 = 1. Then we can rewrite the claim as:
∀n≥1 (\((\sum_{i = 1}^{n}{{Odd}_{i})} = \ n^{2}\)) .
(In other words, (1 + 3 + 5 + 7 + … nth odd integer) = n2.)
The claim appears to be true. Now use induction to prove it. Show the following three steps:
Write an explicit statement of the predicate, which we’ll call P(n).
(Base Case) Prove that P(n) holds for some base case b.
(Induction Step) Prove that, for all integers n ≥ b, P(n) → P(n+1).
P(n) (∑_(i=1)^n▒〖Odd〗_i = n^2)
You should now do steps 2 and 3.
(Step 2, Base Case) Show that P(1) is true. Click here if you’d like to see a solution before you go on to step 3. If clicked, should see:
Base case: 1 is the base case. 1 = 12.
(Step 3, Inductive Step) The first thing to do here is to write out the claim that we’re trying to prove. It looks like the general claim shown as step 3 above, but we need to fill it in for the specific P(n) we are trying to prove. Do it. Then click here to check it before going on. When clicked, should see:
Prove: n 1 ((∑_(i=1)^n▒〖〖Odd〗_i= n^2) 〗 (∑_(i=1)^(n+1)▒〖〖Odd〗_i= (n+1)^2) 〗).
Next, let’s be explicit. Write down the inductive hypothesis. Click here to check it before going on. When clicked, should see:
∑_(i=1)^n▒〖〖(Odd〗_i)= n^2 〗
Now see if you can complete the proof. Click here if you’d like a hint. If clicked, should see:
Observe that the sum of the first n + 1 odd integers is the sum of the first n of them plus the n+1st, so:
[1] (∑_(i=1)^(n+1)▒〖Odd〗_i ) = (∑_(i=1)^n▒〖Odd〗_i ) + 〖Odd〗_(n+1)
Now look at the inductive hypothesis. That’s what we’re going to assume is true for n. Can you use that to rewrite [1]?
When you’re ready, click here to see our proof. When clicked, should see:
The proof of the claim is by induction on n:
Base case: take 1 as the base case. 1 = 12.
Inductive Step:
Prove: n 1 ((∑_(i=1)^n▒〖〖Odd〗_i= n^2) 〗 (∑_(i=1)^(n+1)▒〖〖Odd〗_i= (n+1)^2) 〗).
Observe that the sum of the first n + 1 odd integers is the sum of the first n of them plus the n+1st, so:
\begin{gather*} (∑_(i=1)^(n+1)▒〖〖Odd〗_i)〗 = (∑_(i=1)^n▒〖Odd〗_i ) + 〖Odd〗_(n+1)\\ = Using the induction hypothesis \\ = n2 + 2n + 1 Since is 2(n + 1 – 1) + 1 = 2n + 1. \\ = (n + 1)2 \end{gather*}
Thus, by the Principle of Mathematical Induction:
n 1 (∑_(i=1)^n▒〖〖Odd〗_i= n^2) 〗