Friday, May 8, 2015

Seeing Pattern Seeing Relationship--- Problem Solving Skill

In my previous post(Heuristic-math-problem-solving-skill), I asked the readers to find the sum of the first $n$ terms for the series:

$1+2(1-x)+3(1-x)(1-2x)+4(1-x)(1-2x)(1-3x)+\cdots+n(1-x)(1-2x)\cdots(1-(n-1)x)$

This is one really hard math Olympiad contest problem, but fortunately logical thinking and heuristic problem solving skills are something that we can teach.

When we are encountering such a scene, where we don't know where to begin, we could, as a choice, to work out the sum of first few terms to see if we can spot a pattern from our investigation, and it is always worth bearing in mind that we should show each step instead of simplifying them as we go. This is the golden rule one is advised to follow when we want to discover pattern that might be useful to help us to solve this challenge.

Sum of the first 2 terms:

$\,\,\,\,\,\,1+\underbrace{2(1-x)}$

$=1+2-2x$

$=3-2x$

Sum of the first 3 terms:

$\,\,\,\,\,\, 1+\underbrace{2(1-x)}+\underbrace{3(1-x)(1-2x)}$

$=1+2(1-x)+3(1-3x+2x^2)$

$=6-11x+6x^2$

Sum of the first 4 terms:

$\,\,\,\,\,\,1+\underbrace{2(1-x)}+\underbrace{3(1-x)(1-2x)}+\underbrace{4(1-x)(1-2x)(1-3x)}$

$=1+2(1-x)+3(1-3x+2x^2)+4(1-6x+11x^2-6x^3)$

$=10-35x+50x^2-24x^3$ and so on and so forth...

Can you spot it now? Can you see the following:

Sum of the first 2 terms:

$\,\,\,\,\,\,1+\underbrace{2(1-x)}$

$=1+2-2x$

[MATH]\color{yellow}\bbox[5px,green]{=3-2x}[/MATH]

Sum of the first 3 terms:

$\,\,\,\,\,\,1+\underbrace{2(1-x)}+\underbrace{3(1-x)(1-2x)}$

[MATH]=1+\underbrace{2(1-x)}+\underbrace{3(1-3x+2x^2)}[/MATH]

[MATH]=1+\underbrace{2(1-x)}+\underbrace{3(1-x(3+2x))}[/MATH]

[MATH]=1+2(1-x)+3(1-x\color{yellow}\bbox[5px,green]{(3-2x)}\color{black}{)}[/MATH]

[MATH]\color{yellow}\bbox[5px,purple]{=6-11x+6x^2}[/MATH]

Sum of the first 4 terms:

$\,\,\,\,\,\,1+\underbrace{2(1-x)}+\underbrace{3(1-x)(1-2x)}+\underbrace{4(1-x)(1-2x)(1-3x)}$

$=1+\underbrace{2(1-x)}+\underbrace{3(1-3x+2x^2)}+\underbrace{4(1-6x+11x^2-6x^3)}$

$=1+\underbrace{2(1-x)}+\underbrace{3(1-3x+2x^2)}+\underbrace{4(1-x(6+11x-6x^2))}$

[MATH]=1+2(1-x)+3(1-3x+2x^2)+4(1-x\color{yellow}\bbox[5px,purple]{6-11x+6x^2}\color{black}{)}[/MATH]

Can you see that, if we examine the sum of first 2 terms of the series, i.e.:

$1+2(1-x)=3-2x$,

we can actually relate it to

$(1-x)(1-2x)$ since

$(1-x)(1-2x)=1-3x+2x^2=1-x(3-2x)$

In the case where we want to examine the sum of the first 3 terms, we see that

$1+2(1-x)+3(1-x)(1-2x)=6-11x+6x^2$,

we can actually relate it to

$(1-x)(1-2x)(1-3x)$ since

$(1-x)(1-2x)(1-3x)=1-6x+11x^2-6x^3=1-x(6+11x-6x^2))$

It is not hard to then write down the following:

$1+2(1-x)=3-2x=\dfrac{1-(1-x)(1-2x)}{x}$

$1+2(1-x)+3(1-x)(1-2x)=6-11x+6x^2=\dfrac{1-(1-x)(1-2x)(1-3x)}{x}$

That is to say, we can generate the following conjecture:

The sum of the first $n$ terms $=\dfrac{1-(1-x)(1-2x)\cdots(1-nx)}{x}$.

The rest should be ascertained by proving it to hold for all cases by the induction method.