Proofs Using Mathematical Induction?

Question

How would I find a formula for the sum of the first N natural numbers
and
prove that the sum of the first n cube numbers (i.e. the sum of the cubes of the numbers 1,2,3,...,N) is equal to the square of the sum of the first N natural numbers. (by Mathematical Induction).

Answer 1

for n =1 sum =1^3 =1
RHS = (n(n+1)/2)= 1*2/2 =1
sum of 1st n numbers = n(n+1)/2

so it is true for the 1st step

add (n+1)^3

we need to prove (n(n+1)/2)^2 + (n+1)^3 = ((n+1)(n+2)/2)^2

we get the LHS by adding (n+1)^3 and RHS by putting n+1 for n

LHS = (n+1)^2[(n^2/4 + n+1)
= (n+1)^2/4(n^2+4n+4)
= (n+1)^2(n+2)^2/4
= RHS
we have proved the induction step

hence proved

=

Answer 2

sum of the first n natural numbers

1 + 2 + 3 + ... + N-2 + N-1 + N = ?

What you do (following the young Gauss who solved this problem when he was very young) is to add the N natural numbers to the first series...but, do it in an inverted manner.

1 + 2 + 3 ... + N-2 + N-1 + N
N + N-1 + N-2 ... + 3 + 2 + 1
_______________________________________

(N+1) + (N+1) + (N+1) ... + (N+1 ) + (N+1) + (N+1)

we have the same sum for every term (and there are N terms)

so, we have S = (N + 1) (N)

But, we have to consider that instead of adding the first N natural numbers, we added them twice! So, we have to divide by two. hence,

S = (N + 1) (N)
_________
2


Mathematical Induction.

Prove that, the sum of the cubes of the numbers 1,2,3,...N is equal to the square of the sum of the first N natural numbers

1^3 + 2^3 + 3^3 + .....+ n^3 = (1 + 2 + 3 + .... + N) ^2

Follow the following steps:
1. Prove that the formula is true for n = 1.

1^3 = 1^2 True, since 1 = 1

2. Assume that the formula is true for n = k

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

The right hand side becomes the square of ((k)(k+1) / 2) (which is the reason why you were asked to come up with a formula for the first n numbers. The formula follows from above)

3. Add the (k+1) th term

1^3 + 2^3 + 3^3 + .....+ k^3 + (k+1)^3 = Sum of the k+1 terms, which is equal to ((k+1)(k+2))^2 / 4

4. Then, we subtract the equation in our number 3 from the equation in number 2, so we have

(k+1)^3 = ((k+1)(k+2))^2 / 4 - ((k)(k+1))^2 / 4

Simplifying, we have (multiplying by 4)

4 (k+1)^3 = ((k+1)(k+2))^2 - ((k)(k+1))^2

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

Proving the statement.

Answer 3

sum of the first N natural numbers = n(n+1)/2

Answer 4

You don't need induction for the first ons.
S = 1 + 2 + ................n and
S = n + (n-1) + ............. n so adding them together
2S = (n+1)+(n+1).........(n+1) n times, so
2S = n*(n+1) and
S = n*(n+1)/2

For the 2'nd one, show that for n=1 it's true (trivially, by inspection). Now show that if it's true for some n, it must be true for n+1 and you're done. (No, I'm not going to do it for you. You have to learn to think somewhere along the line and this is a good place to start ☺)

Doug

Answer 5

RTP
∑ n^3 = [ ∑ n]^2

For n = 1
LHS = 1
RHS = 1

So assume it holds for n = k
ie ∑ k^3 = [ ∑ k]^2
or 1 + 2^3 + ... + k^3 = [ k/2 * (1+k)]^2
add (k+1)^3 to both sides

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

Proved

Answer 6

sum(c=1...n)c = n(n+1)/2
proof by induction. true for n = 1.
assume true for n.
sum(c= 1...n+1)c = sum(c=1...n)c + n+1 = (by induction hypothesis) n(n+1)/2 + n+1 = n(n+1)+2(n+1)/2 = (n+1)(n+2)/2
therefore true for n+1.
therefore true for all positive n.

sum(c=1...n)c^3 = ((n(n+1)/2)^2
true for n=1.
assume true for n.
sum(c=1...n+1)c^3 = sum(c=1...n)c^3 + (n+1)^3 = (by induction hypothesis) n(n+1)/2)^2 + (n+1)^3 = (n^2(n+1)^2)/4 +(n+1)^3 = (n^2 +4(n+1))(n+1)^2)/4 = (n^2+4n+4)(n+1)^2)/4 =
(n+2)^2(n+1)^2/4 = ((n+2)(n+1)/2)^2. therefore true for n+1.
by induction, true for all positive n