OU blog

Personal Blogs

Valentin Fadeev

Summing multiplier

Visible to anyone in the world
Edited by Valentin Fadeev, Sunday, 16 Jan 2011, 23:19

This example illustrates the application of the method of "summing multiplier" to solving certain types in recurrencies. It can be found for instance in the book "Concrete Mathematics" by Graham, Knuth and Patashnik. In its essence it translates the idea of the integrating multiplier from the theory of ODEs.

 

Consider the recurrency:

equation left hand side cap i sub n equals right hand side negative n divided by a times cap i sub n minus one plus one divided by a times x super n times e super a times x

Rewrite it in the form

equation left hand side a times cap i sub n equals right hand side negative n times cap i sub n minus one plus x super n times e super a times x

then multiply both sides by s sub n which is to be determined:

equation left hand side s sub n times a times cap i sub n equals right hand side negative s sub n times n times cap i sub n minus one plus s sub n times x super n times e super a times x

The trick will be done, if we find s sub n satisfying the relation:

equation left hand side negative s sub n times n equals right hand side s sub n minus one times a

Solving for s sub n and expanding recursively we get:

equation left hand side s sub n equals right hand side left parenthesis negative one times right parenthesis super n minus one times a super n divided by n factorial

substituiting into equation:

left parenthesis negative one times right parenthesis super n minus one times a super n plus one divided by n factorial times cap i sub n postfix minus left parenthesis equation left hand side negative one times right parenthesis super n minus two times a super n divided by open n minus one close factorial times cap i sub n minus one equals right hand side left parenthesis negative one times right parenthesis super n minus one times a super n divided by n factorial times x super n times e super a times x

cap i sub zero is easily obtained from the original integral:

equation left hand side cap i sub zero equals right hand side e super a times x minus one divided by a

Summing from 1 to n we get the so called "telescopic sum" on the left side meaning that only the first and the last terms survive:

left parenthesis equation left hand side negative one times right parenthesis super n minus one times a super n plus one divided by n factorial times cap i sub n minus open negative a close times cap i sub zero equals right hand side e super a times x times n ary summation from k equals one to n over left parenthesis negative one times right parenthesis super k minus one times a super k divided by k factorial times x super k

Ultimately solve for cap i sub n :

equation left hand side cap i sub n equals right hand side minus left parenthesis negative one times right parenthesis super n times n factorial divided by a super n plus one left parenthesis equation left hand side one minus e super a times x minus e super a times x times n ary summation from k equals one to n over open negative one times right parenthesis super k times a super k divided by k factorial times x super k close equals right hand side minus left parenthesis negative one times right parenthesis super n times n factorial divided by a super n plus one left parenthesis one minus n ary summation from k equals zero to n over open negative one times right parenthesis super k times a super k divided by k factorial times x super k close equals n factorial e super a times x times n ary summation from k equals zero to n over left parenthesis negative one times right parenthesis super n minus k divided by a super n minus k plus one times k factorial minus left parenthesis negative one times right parenthesis super n times n factorial divided by a super n plus one

(Note that the second term on the right side is the solution for "homogeneous" variant of the equation, i.e. withot x super n times e super a times x term, suggesting another method borrowed from ODEs)

Permalink
Share post