you will be writing a second set of proofs this time inducti

you will be writing a second set of proofs, this time inductive proofs.

Here are the statements you are to prove by induction on n:

13+23++n3=n2(n+1)24, for all n0

12+23++n(n+1)=n(n+1)(n+2)3, for all n0

3n3n, for all n0

2n+12n, for all n3 (Hint: here your base case is n=3)

n22n, for all n4 (Hint: use the previous result to help out)

The Fibonacci sequence is the one defined by

F(0)=0

F(1)=1

F(n)=F(n1)+F(n2) when n2

that is, each element of the sequence (except the first two) is the sum of the previous two elements. Thus, the sequence continues:

F(2)=1,

F(3)=2,

F(4)=3,

F(5)=5,

F(6)=8,

F(7)=13,

F(8)=21, etc.

Prove the following facts about this sequence, for all n0:

F(n)2n

F(0)+F(1)++F(n)=F(n+2)1

F(0)2+F(1)2++F(n)2=F(n)F(n+1)

gcd(F(n+1),F(n))=1 (Hint: Try out the Euclidean algorithm on these two numbers and see what happens)

Solution

To prove: 1^3 + 2^3 + 3^3 + ... + n^3 = [n(n + 1)/2]^2 for all natural numbers n.

Proof (by induction):

The first case is the base Case: Let n = 1.
LHS = 1^3 ... 1^3
= 1 ... 1
= 1

Now we will evaluate the RHS

=> (1(1 + 1)/2)^2
= 1(2/2)^2
= 1(1)^2
= 1(1)
= 1

Since,LHS = RHS, so the formula holds true for n = 1.

Induction Hypothesis:Now let us assume the formula holds true for up to n = k. That is, assume that

1^3 + 2^3 + 3^3 + ... + k^3 = [k(k + 1)/2]^2

(Now we will have to prove that the formula holds true for n = k + 1, i.e. we want to prove that

1^3 + 2^3 + 3^3 + ... + (k + 1)^3 = [(k + 1)((k + 1)+ 1)/2]^2 )

However the sum of (k + 1) terms in the sum is the same as the sum of k terms, plus an extra term.

This can be expressed as:

1^3 + 2^3 + 3^3 + ... + (k + 1)^3 = {1^3 + 2^3 + ... + k^3} + (k + 1)^3


= [k(k + 1)/2]^2 + (k + 1)^3

Firstly we will square each term for the first term.

= [(k^2)(k + 1)^2]/4 + (k + 1)^3

The next step is to put the second term with a denominator of 4.

= [(k^2)(k + 1)^2]/4 + [4(k + 1)^3]/4

Finally we will do the factoring [ (k + 1)^2 ] / 4.

= ( [(k + 1)^2]/4 ) ( [(k^2)] + [4(k + 1)] )

The next step is to simplif the stuff in the second brackets,

= ( [(k + 1)^2]/4 ) (k^2 + 4k + 4)

Factoring the second brackets,

= ( [(k + 1)^2]/4 ) (k + 2)^2

We have all squared terms again. Express this as one square.

= [ (k + 1)(k + 2)/2 ]^2

The next step is to express express 2 as 1 + 1.

= [ (k + 1)(k + 1 + 1)/2 ]^2

Therefore,

1^3 + 2^3 + 3^3 + ... + (k + 1)^3 = [ (k + 1)(k + 1 + 1)/2 ]^2

This is how we have shown that the formula holds true for n = k + 1.

Therefore, by the Principle of Mathematical Induction,

1^3 + 2^3 + 3^3 + ... + n^3 = [n(n + 1)/2]^2 for all natural numbers n.