Thread: Induction Proof

Here is the problem:

"Let S_n stand for the sum of all the products of the integers, taken two at a time, from 1 to n. For example, S_4 means:

S_4 = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4

Prove that S_n is given explicitly by:

S_n = [n*(n^2-1)*(3*n+2)]/24".

So, I was thinking this was the perfect candidate for an induction proof. I thought it would be best to derive the formula first:

Derive formula S_(n+1) = S_n + 1(n+1) + 2(n+1) + ... + n(n+1)
= S_n + n(n + 1)^2 / 2

Now what; base case of course works out. How do I work toward the induction assumption.

Originally Posted by AfterShock

Here is the problem:

"Let S_n stand for the sum of all the products of the integers, taken two at a time, from 1 to n. For example, S_4 means:

S_4 = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4

Prove that S_n is given explicitly by:

S_n = [n*(n^2-1)*(3*n+2)]/24".

So, I was thinking this was the perfect candidate for an induction proof. I thought it would be best to derive the formula first:

Derive formula S_(n+1) = S_n + 1(n+1) + 2(n+1) + ... + n(n+1)
= S_n + n(n + 1)^2 / 2

Now what; base case of course works out. How do I work toward the induction assumption.

Suppose that for some that



Now you need to show that:

.

But you already know that:



So you need to show that the RHS of is equal to the
RHS of . Then you will have shown that if the formula for
is true for some it is true for . Which is what
you need with the base case to complete the proof.

RonL