# Induction Proof

Printable View

• May 6th 2006, 08:51 PM
AfterShock
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.
• May 6th 2006, 11:32 PM
CaptainBlack
Quote:

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 $k \ge 2$ that

$S_k = \frac{k(k^2-1)(3k+2)}{24}$

Now you need to show that:

$S_{k+1}=\frac{(k+1)((k^2+2k)(3k+5)}{24}\ \ \ \dots (1)$.

But you already know that:

$S_{k+1}=S_k + \frac{k(k + 1)^2}{ 2}=$ $\frac{k(k^2-1)(3k+2)}{24} + \frac{k(k + 1)^2}{ 2}\ \ \ \dots (2)$

So you need to show that the RHS of $(1)$ is equal to the
RHS of $(2)$. Then you will have shown that if the formula for
$S_k$ is true for some $k \ge 2$ it is true for $k+1$. Which is what
you need with the base case to complete the proof.

RonL
All times are GMT -8. The time now is 03:32 PM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 10, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9245322942733765, "perplexity_flag": "middle"}