Problem 3
Use mathematical induction to prove that
1 3 + 2 3 + 3 3 + ... + n 3 = n 2 (n + 1) 2 / 4
for all positive integers n.
Answers
1 3 + 2 3 + 3 3 + ... + n 3 = n 2 (n + 1) 2 / 4
STEP 1: We first show that p (1) is true.
Left Side = 1 3 = 1
Right Side = 1 2 (1 + 1) 2 / 4 = 1
hence p (1) is true.
STEP 2: We now assume that p (k) is true
1 3 + 2 3 + 3 3 + ... + k 3 = k 2 (k + 1) 2 / 4
add (k + 1) 3 to both sides
1 3 + 2 3 + 3 3 + ... + k 3 + (k + 1) 3 = k 2 (k + 1) 2 / 4 + (k + 1) 3
factor (k + 1) 2 on the right side
= (k + 1) 2 [ k 2 / 4 + (k + 1) ]
set to common denominator and group
= (k + 1) 2 [ k 2 + 4 k + 4 ] / 4
= (k + 1) 2 [ (k + 2) 2 ] / 4
We have started from the statement P(k) and have shown that
1 3 + 2 3 + 3 3 + ... + k 3 + (k + 1) 3 = (k + 1) 2 [ (k + 2) 2 ] / 4
Which is the statement P(k + 1).
When you prove something by induction, after showing the base case (1<311<31), you want to assume the statement is true for some integer k∈Z+k∈Z+. Therefore, we want to start out by saying that for this integer kk, we know that it is true that k<3kk<3k.
We want to prove that k+1<3k+1k+1<3k+1, and it is important in this case to use our assumption that k<3kk<3k. You have the correct intuition to take this assumption, and modify it to get closer to what we want to prove. You correctly deduced that
k+1<3k+1.
k+1<3k+1.
We want to prove that 3k+1<3k+13k+1<3k+1. It is important to remember that power of integers is just a fancy way of writing repeated multiplication. That is,
xn=x⋅x⋅…⋅x (n times)
xn=x⋅x⋅…⋅x (n times)
or that xn=xn−1⋅x
or that xn=xn−1⋅x
This tells us that 3k+13k+1 = 3⋅3⋅…⋅33⋅3⋅…⋅3 a total of k+1k+1 times, which is equal to saying 3k+1=3k⋅33k+1=3k⋅3. Now, how can we represent 3k⋅33k⋅3 in a form we can compare to 3k+13k+1? Well, just like exponents, multiplication of integers is just a fancy way of writing repeated addition:
n⋅x=x+x+…+x (n times).
n⋅x=x+x+…+x (n times).
This tells us that 3k⋅3=(3k+3k+3k)3k⋅3=(3k+3k+3k). Maybe this form will be easier to work with! Let's return to what we want to prove. Using our new form, we want to show that
3k+1<3k+3k+3k.