Concrete Mathematics Notes: Summation by Parts

Just a quick note to more verbosely explain some things that took a while to sink in. This post primarily concerns page 55 of Concrete Mathematics (Knuth, Graham, Patashnick) where they derive Summation by Parts.

Applying Difference Operator to Product of Two Functions

This is equation 2.54 and, at first, I did not understand the second step especially the section highlighted in blue

\[\begin{align} \Delta(u(x)v(x)) &= u(x+1)v(x+1) - u(x)v(x) \\ &= u(x+1)v(x+1) \boldsymbol{\color{blue}{- u(x)v(x+1) + u(x)v(x+1)}}\color{#3d4144} - u(x)v(x) \\ &= u(x)\Delta v(x) + v(x+1)\Delta u(x) \end{align}\]

My initial reaction was: wtf is the new terms above? Had me stumped for a while I must confess.. Then I realised they were just cancelling out extras conjured into existence like a quickly annihilating virtual particle/anti-particle in the quantum vacuum. These “nothing terms” are used for factoring to arrive at our difference-of-a-product form at 2.54 in the book. So, more verbosely, the factoring step is in blue this time:

\[\begin{align} \Delta(u(x)v(x)) &= u(x+1)v(x+1) - u(x)v(x) \\ &= u(x+1)v(x+1) - u(x)v(x+1) + u(x)v(x+1) - u(x)v(x) \\ &= \boldsymbol{\color{blue}v(x+1)(u(x+1) - u(x)) + u(x)(v(x+1) - v(x))\color{#3d4144}} \\ &= v(x+1)\Delta u(x) + u(x)\Delta v(x) \\ &= u(x)\Delta v(x) + v(x+1)\Delta u(x) \end{align}\]

Last two lines just swapped to end up where the book does. This seemed kind of magical to me but, I suppose, it works due to the commutative and associative laws of addition/multiplication. I even tried it out with actual numbers and it works :D

Deriving Actual Summation by Parts

My next moment of confusion came when deriving the actual summation by parts. We start with the compact rule for difference of a product using the $E$ “nuisance” (quoting the book here :) ):

\[\Delta(uv) = u\Delta v + Ev\Delta u\]

Then they say:

Taking the indefinite sum on both sites of this equation, and rearranging its terms, yields the advertised rule for summation by parts:

\[\sum u\Delta v = uv - \sum Ev\Delta u\]

I get the rearrangement of terms but how $\Delta(uv)$ becomes $uv$ was a bit of a mystery. After the requisite amount of time overthinking it, it is just literally following through the steps of turning $\Delta(uv)$ into $-\Delta(uv)$ when re-arranging; then shaking things out. I find it useful to expand everything and go from there:

\[\begin{align} -\Delta(uv) &= -\Delta(u(x)v(x)) \\ &= -(u(x+1)v(x+1) - u(x)v(x)) \\ &= -u(x+1)v(x+1) + u(x)v(x) \\ &= -u(x)v(x) \\ &= -uv \\ \end{align}\]

Then, in 2.56 in the book, the rearrangment part makes it positive:

\[\begin{align} \Delta(uv) &= u\Delta v + Ev\Delta u \\ -u\Delta v &= -\Delta(uv) + Ev\Delta u \\ u\Delta v &= \Delta(uv) - Ev\Delta u \end{align}\]

Finally they take the indefinite sum on both sides giving us the summation by parts rule

\[\sum u\Delta v = \Delta(uv) - \sum Ev\Delta u\]