Personal Blogs

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:

Rewrite it in the form

then multiply both sides by which is to be determined:

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

Solving for and expanding recursively we get:

substituiting into equation:

is easily obtained from the original integral:

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:

Ultimately solve for :

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