Question

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.

Answer 1

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).

Answer 2

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.