## Monday, January 16, 2012

### JCCDQBHWHSS076 Telescoping Sum and Inequalities

 [original source unknown]

Introduction
In keeping the spirit of discussing genuinely “hard core” Singapore school mathematics (not “Singapore Math”, the Americanised parody) in this blog, I discuss a particularly “pernicious” problem on summation, taken from a book whose authors did not bother to credit the questions’ source.  Aside: Do you wonder why these guys never get caught for copyright infringement, and why they can get away with selling these books blatantly at a popular book chain?  My theory is that the police officers or lawyers themselves have children who are also struggling with maths … and they “need” these examination-paper compilations … so … .
Anyway, do not be overwhelmed when you encounter a question like this that seems out of your reach.  Good problem solving involves not just regurgitating formulas and performing set procedures, but knowing how to react when one encounters unfamiliar problems.  There are also some examination-paper compilations (illegally) sold at road-side stalls at various places in Singapore.  They often provide full solutions copied straight from teachers’ marking schemes.  However, even if you have the full solutions, they may not explain how these solutions were obtained.  In this article (as in others), I will reveal how we can tackle hard questions like this using metacognition and heuristics

First Part of the Question

Stage 1 – Understanding

What are you required to do?
I am required to show that the first expression is equal to the second one.

Stage 2 – Planning

What can you do?
This looks like a partial fractions problem.  However, it looks pretty nasty.  We have two quadratic denominators …  Are they factorisable?  No, at least not with “nice numbers” (integer coefficients) … which means we might need something like  An+B  over  n2 – 3n + 1 and then  Cn+D  over  n2 + n – 1.  Then we solve for four unknowns  A, B, C, D.  Yulk!  This does not look like fun.

Is there another way or a better way?
Hmmmm … *thinking hard* … We do not really need to solve for A, B, C and D.  Actually we can think of this “show/ prove” question as something in which the answer is already given (viz. the second expression).  We need to show that the first expression is equal to this.  But we can do it by doing it the other way round.  If we can show that the second expression is equal to the first expression, then of course the first expression is equal to the second expression.  Bingo!

Stage 3 – Execution

 Figure 1 – 1st part of the question
Comment: Most of this is just secondary school algebra, which JC students are expected to be adept at already.  Mentioning the “Symmetric Law of Equality” (not in any Singapore school syllabus, but it is just “common sense” made to look more official) is meant to impress teachers and convince the die-hard skeptics that this “unorthodox” method is indeed a valid method.  But then, most likely, the “unorthodox” teacher who set this “unorthodox” exam question probably expected you to do it by this “unorthodox” method anyway.

Stage 4 – Evaluation

Have you done it correctly?
Yeah!  Got it, as required!

Second Part of the Question

Stage 1 – Understanding

What are you required to do?
To find (i.e. evaluate) the expression given in sigma (S) notation.

What will the answer look like?  Will it be a number?
No.  It will be an expression ...  In terms of?  … capital ‘N’.  What about the small ‘n’?  This is just the summation index, which is a dummy variable i.e. it is a temporary “use-and-then-throw-away” variable for the sigma notation, but it will not appear in the final answer.

What concept is this part of the question testing you on?  How do you know?
This part of the question is testing me on “the Method of Differences” technique (also known as “the Telescoping Sum” technique).  I know this because it is a favorite technique of the teachers and ‘A’ level examiners, as a huge variety of questions can be set based on this technique.  Actually the major clue is in the first part of the question, where a difference between two expressions is involved.  The minus ‘–’ sign in the second expression is the dead giveaway, the “smoking gun”.

Stage 2 – Planning

What are you going to do?
Once I have diagnosed this problem as a “method of differences” problem, it is just a matter of following the SOP (Standard Operating Procedure):  Expand the sigma notation by writing out explicitly the first few terms and the last few terms.  Then look for a cancellation pattern.  After cancelling, there will be some terms from the front bit and some terms from the end bit remaining.

Stage 3 – Execution

Some rough working seems necessary:-
When  n = 3:   n2 – 3n + 1  = … =  1,   n2 + n – 1   = … = 11
When  n = 4:   n2 – 3n + 1  = … =  5,   n2 + n – 1   = … = 19
When  n = 5:   n2 – 3n + 1  = … = 11,   n2 + n – 1   = … = 29
When  n = 6:   n2 – 3n + 1  = … = 19,   n2 + n – 1   = … = 41

When  n = N – 1:
n2 – 3n + 1  =  (N – 1)2 – 3(N – 1) + 1  =  N 2 – 5N + 5
n2 + n – 1   =  (N – 1)2 + (N – 1) – 1   =  N 2N – 1
When  n = N
n2 – 3n + 1  =  N 2 – 3N + 1
n2 + n – 1   =  N 2 + N – 1

 Figure 2 – Telescoping Sum Method (a.k.a. Method of Differences)

From the given expression (line #1), we replace the summand by the difference expression (line #2) found in the earlier part of the question.  We expand the sigma notation by writing out the first four differences  (by substituting n = 3, 4, 5, 6)
and the last two differences  (by substituting n = N–1, N).  From experience, I know that I can see the pattern more clearly if I write the terms neatly, devoting one row per value of n I substitute.  Indeed once I do that, the cancellation pattern becomes obvious.  In the last two lines, I collect the remaining (uncancelled) terms and simplify the resulting expression.

Stage 4 – Evaluation / Checking

Are you correct?  How do you check?
Yes.  I can check by substituting, say, (capital letter) N = 3, 4, 5 and seeing if the expressions agree.

Third (Final) Part of the Question

Stage 1 – Understanding

What are you required to do?
To show that the given sum to infinity is less than 1.

What type of question is this?
This is a “show / prove” question involving inequalities and sum to infinity.

Stage 2 – Planning

Do you notice anything?  How is it connected to the earlier part(s) of the question?
This looks hard.  The connection (if any) is not obvious.

What are you going to do about it?
There is a pattern.  I’ll solve part of the problem (this is a heuristic) by considering a finite sum first.  Later on, I can let  N®¥  to get the sum to infinity.  I rewrite it in sigma notation to try to see if there is any connection with the previous part.  I need to slowly manipulate this (“massaging the expression”) to make it look like the expression in previous part.  But … hmmm … this looks quite different from the earlier sigma expression …
 Figure 3 – Using finite sum and sigma notation
What are the differences?  Can you point them out?
 Figure 4 – Doing a comparison (“Spot the differences”)

(D1) instead of starting from  n = 3, this sum starts from  n = 1
(D2) there is no ‘2’ in the numerator, unlike the previous summation
(D3) there is no ‘(2n –1)’ in the numerator, unlike the previous summation
(D4) in the denominator, the smaller quadratic is  n2  instead of  n2 – 3n + 1
(D5) in the denominator, the larger quadratic is  (n + 1) 2  instead of  n2 + n – 1
Hmmmm … it looks like the person who set this question has set up a minefield.  If I get it wrong in any one of the above, the question will blow me off.

Don’t panic.  What heuristic can you use?
I can split this big problem into smaller problems.  I can handle it a step at a time.

So how can you handle (D1)?

I can write out the first two terms explicitly and start the summation from  n = 3.
How do you that?  Just substitute n = 1  and then  n = 2  into the summand’s formula to get the first two terms.  For the rest of the terms, I write it in a similar sigma form, but starting from n = 3.

Stage 3 – Execution
 Figure 5 – dealing with the big problem in smaller steps

Back to Stage 2 – Planning

Good.  Now, how do you deal with (D2)?

I can forcefully introduce a ‘2’ in the numerator, and compensate that by putting a factor of ½, which can be written outside the summation.  Further, I can also evaluate ¼ + 1/36, which is  10/36.

Stage 3 – Execution
 Figure 6 – dealing with the 2nd sub-problem

Back to Stage 2 – Planning

Now, how to deal with (D3)?
I can forcefully introduce a ‘(2n –1)’ in the numerator …

But wouldn’t that be different from the previous equation?
Yes.  In fact, the new expression would be bigger.  Why?
For  n = 3, 4, 5, …,  each of the  2n –1  will be at least 5 … definitely more than 1.  Multiplying with the positive summands, each term in the summation will be bigger than before.  Hence the resulting summation will be bigger than the previous line’s summation.  That means I need to replace the ‘=’ sign with the ‘<’ sign.

Stage 3 – Execution
 Figure 7 – dealing with the 3rd sub-problem

Back to Stage 2 – Planning

How to deal with (D4) and (D5)?
Now this is a tough cookie … hmmm …

Can you compare the pairs of denominators?  For (D4), which is bigger one?
Comparing  n2  with  n2 – 3n + 1,  it looks like the latter is smaller because there is a minus  3n.  So  n2  is larger.  By how much?  If  n2 – ¿¿¿ = n2 – 3n + 1,
what is the ‘¿¿¿’?  By inspection (i.e. fiddling with the algebra) we observe that
n2 – (3n – 1) = n2 – 3n + 1
So the  ‘¿¿¿’ is  3n – 1.  Is this positive?  Yes, for n = 3, 4, 5, …, this is at least 8.  Definitely positive.  Which means  n2  is indeed greater than  n2 – 3n + 1, and it is bigger by  3n – 1.

(n + 1) 2  is the same as  n2 + 2n + 1.  Hence
n2 + n – 1 = (n + 1) 2n – 2 = (n + 1) 2 – (n + 2)
That means  (n + 1) 2  is more than  n2 + n – 1, and it is bigger by  (n + 2).

So, are the target denominators  n2 – 3n + 1  and  n2 + n – 1   bigger or smaller than what we have currently?  These denominators are smaller.

Will the resulting expression be bigger or smaller?
By the “Monk-Porridge Theorem”, since we are dividing positive quantities by smaller divisors, we will end up with a larger quantity.  So we link to the resulting expression with a ‘<’.

Stage 3 – Execution
 Figure 8 – dealing with the last two sub-problems

Stage 4 – Evaluation

Does this make sense?
Yes.  This inequality sign ‘<’ is in the same direction as the previous one.
We are using the Law of Transitivity: if  a < b  and  b < c  (conventionally we write this as  a < b < c), then  a < c.  If the inequality signs are in different directions (say,  a < b  and  b > c), then we are in trouble, because we cannot conclude that  a < c.  Here, the inequality signs point the same way, so we are good.  We can go back to stage 3 to complete the rest of the calculations.

Back to stage 3 – Execution
 Figure 9 – completing the question

In line #1, we simplify the previous expression.  Then using the earlier result obtained from the second part of the question, we replace the sigma expression with its equivalent, shown in line #2 between the curly braces.  We have two expressions that are reciprocals of quadratics in ‘N’.  Obviously, these become smaller and smaller as  N becomes larger and larger.  In other words, these terms tend to zero as  N  tends to infinity (line #3).  Hence the infinite sum will tend to something less than 79/90 (we can work this out from the line #2 expression).  This is definitely less than 1, which is what we are supposed to demonstrate.

Final Presentation (for the last part of the question)
 Figure 10 – putting it all together

Step 5 – Reflection

What did you learn by doing this question?

I learned that, once again, metacognition and heuristics are useful for the 5-stage problem solving process.  For a complicated problem, one does not have to proceed with the five stages in a strictly linear fashion.  Instead of trying to regurgitate a fixed technique where there is none, I can go back and forth (especially between stages 2 and 4), thinking, doing and re-thinking along the way.  This is the usual way expert mathematics solvers actually solve their mathematics problems, not that they have a method that automatically proceeds from start to finish.
From the first part of this question, I learned to look out for shortcuts.  We can use the Symmetric Law of Equality (A = B Þ B = A) instead of doing things by the usual way (partial fractions).
From the second part of this question, I learned to be aware of questions that test the “Method of Differences” (or the “Telescoping Sum” technique).  In this question, the tell-tale giveaway clue is the ‘–’ minus sign.  Once you know it is the “Method of Differences”, the execution of this technique is rather standard.  Write out the terms by substituting the first few values of the summation index (n in this case) and the last few values.  Use one row per value of  n, so that the cancellation pattern can be seen more clearly.  After all the gory cancellations, a few of the first terms and a few of the last terms remain.
For the last part of the question, I learned to keep calm in the face of difficulties.  I learned to simplify the question and rephrase the question (e.g. by rewriting it into sigma notation).  I look for patterns.  I learned that making comparisons (“what I have” vs “what I want”) is a powerful heuristic that can suggest what steps to take next.  I also learned that a complicated question can be tackled by breaking it down into smaller, more manageable sub-problems.  Then I deal with these sub-problems systematically.

What about you, the reader?  What did you learn from this problem?

Remarks
The term “Telescoping Sum” comes from the observation that when applying the method of differences, you begin with a long expression like a telescope that is stretched out.  After cancellation of the terms in the middle, the expression is being shorted – just like compressing a telescope.