Further On A Calculus Of Differences

| 0 Comments

As I have previously reported[1], my fellow students and I have found our curiosity drawn to the calculus of sequences, in which we define analogues of the derivatives and integrals of functions for a sequence \(s_n\) with the operators
\[ \Delta \, s_n = s_n - s_{n-1} \]
and
\[ \Delta^{-1} \, s_n = \sum_{i=1}^n s_i \]
respectively, where \(\sum\) is the summation sign, for which we interpret all non-positively indexed elements as zero.

I have already spoken of the many and several fascinating similarities that we have found between the derivatives of sequences and those of functions and shall now describe those of their integrals, upon which we have spent quite some mental effort these last few months.

Integrals Of Some Elementary Sequences

Just as we did for our sequence differential operator, we chose to first apply our sequence integral operator to some simple sequences to see how its results compared to those of the more familiar function integral operator. To begin, given a constant sequence
\[ s_n = c \]
we have
\[ \Delta^{-1} \, s_n = \sum_{i=1}^n c = c \times n \]
very much as we have for the integral of a constant function
\[ \int_0^n \, c \, \mathrm{d}x = [c \times x]_0^n = c \times n - c \times 0 = c \times n \]
We next considered the identity sequence, for which
\[ \begin{align*} s_n &= n\\ \Delta^{-1} \, s_n &= \sum_{i=1}^n i = \tfrac12 n (n+1) = \tfrac12 n^2 + \tfrac12 n \end{align*} \]
as is easily verified by taking its derivative
\[ \begin{align*} \Delta \left(\Delta^{-1} \, s_n\right) &= \Delta^{-1} \, s_n - \Delta^{-1} \, s_{n-1}\\ &= \left(\tfrac12 n^2 + \tfrac12 n\right) - \left(\tfrac12 (n-1)^2 + \tfrac12 (n-1)\right)\\ &=\left(\tfrac12 n^2 + \tfrac12 n\right) - \left(\tfrac12 (n^2-2n+1) + \tfrac12 (n-1)\right)\\ &= \tfrac12 n^2 + \tfrac12 n - \tfrac12 n^2 + n - \tfrac12 - \tfrac12 n + \tfrac12\\ &= n \end{align*} \]
This too bears a striking resemblance to the equivalent function integral
\[ \int_0^n x \, \mathrm{d}x = \left[\tfrac12 x^2\right]_0^n = \tfrac12 n^2 \]
Similarly, we found for the sequence of squares that
\[ \begin{align*} s_n &= n^2\\ \Delta^{-1} \, s_n &= \sum_{i=1}^n i^2 = \tfrac13 n^3 + \tfrac12 n^2 + \tfrac16 n \end{align*} \]
which certainly suggests that the sequence integrals of non-constant monomials, being those sequences whose terms are strictly positive powers of their indices, have the same relationship with function integrals as did their sequence derivatives with function derivatives, in that their highest order terms are equal to the results of their function equivalents, a similarity that we might express as
\[ \begin{align*} O\left(\Delta \, n^k\right) &= \frac{\mathrm{d}x^k}{\mathrm{d}x} \bigg|_n = k \times n^{k-1}\\ O\left(\Delta^{-1} \, n^k\right) &= \int_0^n x^k \, \mathrm{d}x = \tfrac{1}{k+1} n^{k+1} \end{align*} \]
where \(O\) should be read as the highest order of and the vertical bar stands for the value of the derivative upon its left hand side when \(x\) is equal to the value at the foot of its right hand side.

Integrals Of Monomial Sequences

To figure whether or not this relationship does indeed hold true in general, my fellow students and I first noted that
\[ \sum_{i=1}^n (i+1)^{k+1} - i^{k+1} = (n+1)^{k+1} - 1 \]
since the left hand side of the \(i^\mathrm{th}\) subtraction is cancelled out by the right hand side of the \((i+1)^\mathrm{th}\), leaving just the left hand side of the first and the right hand side of the last. Expanding out the powers of \(i+1\) and \(n+1\) yields
\[ \sum_{i=1}^n \left(\sum_{r=0}^{k+1} {^{k+1}}C_r \, i^{k+1-r}\right) - i^{k+1} = \left(\sum_{r=0}^{k+1} {^{k+1}}C_r \, n^{k+1-r}\right) - 1 \]
where \({^k}C_r\) is the combination which counts the number of ways in which we can select \(r\) items from \(n\) when the order of choosing is not taken into consideration with
\[ {^k}C_r = \frac{k!}{r! \times (k-r)!} = {^k}C_{k-r} \]
where the exclamation mark stands for the factorial, the product of every number from one up to the term upon its left. By convention the factorial of zero is equal to one and so we have
\[ \begin{align*} {^{k+1}}C_0 &= \frac{(k+1)!}{0! \times (k+1-0)!} = \frac{(k+1)!}{(k+1)!} = 1\\ {^{k+1}}C_{k+1} &= {^{k+1}}C_{(k+1)-(k+1)} = {^{k+1}}C_0 = 1 \end{align*} \]
and so we are subtracting the first and last terms of the sums over \(r\) on the left and right hand sides of the equals sign respectively which results in
\[ \begin{align*} \sum_{i=1}^n \sum_{r=1}^{k+1} {^{k+1}}C_r \, i^{k+1-r} &= \sum_{r=0}^k {^{k+1}}C_r \, n^{k+1-r}\\ \sum_{r=1}^{k+1} {^{k+1}}C_r \sum_{i=1}^n i^{k+1-r} &= \sum_{r=0}^k {^{k+1}}C_r \, n^{k+1-r}\\ \sum_{r=1}^{k+1} {^{k+1}}C_r \, \Delta^{-1} \, n^{k+1-r} &= \sum_{r=0}^k {^{k+1}}C_r \, n^{k+1-r} \end{align*} \]
Bringing out the first terms of these sums and rearranging yields
\[ \begin{align*} {^{k+1}}C_1 \, \Delta^{-1} \, n^{k+1-1} + \sum_{r=2}^{k+1} {^{k+1}}C_r \, \Delta^{-1} \, n^{k+1-r} &= {^{k+1}}C_0 \, n^{k+1-0} + \sum_{r=1}^k {^{k+1}}C_r \, n^{k+1-r}\\ (k+1) \, \Delta^{-1} \, n^{k+1-1} &= n^{k+1} + \sum_{r=1}^k {^{k+1}}C_r \, n^{k+1-r} - \sum_{r=2}^{k+1} {^{k+1}}C_r \, \Delta^{-1} \, n^{k+1-r}\\ &= n^{k+1} + \left({^{k+1}}C_1 \, n^{k+1-1} + \sum_{r=2}^k {^{k+1}}C_r \, n^{k+1-r}\right)\\ &\phantom{=n^{k+1}} \; - \left(\sum_{r=2}^k {^{k+1}}C_r \, \Delta^{-1} \, n^{k+1-r} + {^{k+1}}C_{k+1} \, \Delta^{-1} \, n^0\right)\\ &= n^{k+1} + (k+1) \, n^k + \sum_{r=2}^k {^{k+1}}C_r \, \left(n^{k+1-r} - \Delta^{-1} \, n^{k+1-r} \right) - n \end{align*} \]
and so, finally, we find that
\[ \begin{align*} \Delta^{-1} \, n^k &= \tfrac{1}{k+1} n^{k+1} + n^k - \tfrac{1}{k+1} n + \sum_{r=2}^k \frac{{^{k+1}}C_r}{k+1} \, \left(n^{k+1-r} - \Delta^{-1} \, n^{k+1-r} \right)\\ &= \tfrac{1}{k+1} n^{k+1} + n^k - \tfrac{1}{k+1} n + \sum_{r=1}^{k-1} \frac{{^{k+1}}C_{r+1}}{k+1} \, \left(n^{k-r} - \Delta^{-1} \, n^{k-r} \right) \end{align*} \]
for \(k\) greater than zero.

For example, for \(k\) equal to one we have
\[ \Delta^{-1} \, n = \tfrac12 n^2 + n - \tfrac12 n = \tfrac12 n^2 + \tfrac12 n \]
and for \(k\) equal to two
\[ \begin{align*} \Delta^{-1} \, n^2 &= \tfrac13 n^3 + n^2 - \tfrac13 n + \frac{{^3}C_2}{3} \left(n - \Delta^{-1} \, n\right)\\ &= \tfrac13 n^3 + n^2 - \tfrac13 n + n - \Delta^{-1} \, n\\ &= \tfrac13 n^3 + n^2 - \tfrac13 n + n - \left(\tfrac12 n^2 + \tfrac12 n\right)\\ &= \tfrac13 n^3 + \tfrac12 n^2 + \tfrac16 n \end{align*} \]
in accordance with the formulae that my fellow students and I had derived for these integrals.

To reassure ourselves that we had figured correctly we put together deck 1 to compare the results of this formula to the sums of sequences whose terms are greater powers of their indices.

Deck 1: The Monomial Series Integral

That they differ by small quantities we are quite confident is merely a consequence of the effect of limited precision arithmetic upon the formula's results.

Emboldened by this success, we proceeded to construct a deck to calculate the coefficients implied by this formula for the polynomial sequences that are the integrals of monomial sequences, utilising the facility for rational arithmetic[2] provided by ak.rational so as to avoid the deleterious effects of that limited precision.

Deck 2: Monomial Series Integral Polynomials

Note that, as with the sequence derivative, it is trivially the case that for sequences \(s_n\) and \(t_n\) and constants \(a\) and \(b\)
\[ \Delta^{-1} \, \left(a \times s_n + b \times t_n\right) = a \times \Delta^{-1} \, s_n + b \times \Delta^{-1} \, t_n \]
since
\[ \Delta^{-1} \, \left(a \times s_n + b \times t_n\right) = \sum_{i=1}^n a \times s_n + b \times t_n = \sum_{i=1}^n a \times s_n + \sum_{i=1}^n b \times t_n = a \times \sum_{i=1}^n s_n + b \times \sum_{i=1}^n t_n \]

Integration By Parts

The next question that my fellow students and I asked ourselves was what form might the sequence equivalent of the rule of integration by parts take, which for a pair of functions \(f\) and \(g\) states that
\[ \int f \times \frac{\mathrm{d}g}{\mathrm{d}x} \, \mathrm{d}x = \bigg[f \times g\bigg] - \int \frac{\mathrm{d}f}{\mathrm{d}x} \times g \, \mathrm{d}x \]
After some consideration we realised that
\[ \begin{align*} \Delta^{-1} \, \left(s_n \times \Delta \, t_n\right) &= \sum_{i=1}^n s_n \times \left(t_n - t_{n-1}\right) = \sum_{i=1}^n s_n \times t_n - s_n \times t_{n-1}\\ &= \sum_{i=1}^n s_n \times t_n - s_n \times t_{n-1} - \left(s_{n-1} \times t_{n-1} - s_{n-1} \times t_{n-1}\right)\\ &= \sum_{i=1}^n \left(s_n \times t_n - s_{n-1} \times t_{n-1}\right) - \left(s_n \times t_{n-1} - s_{n-1} \times t_{n-1}\right)\\ &= \sum_{i=1}^n \left(s_n \times t_n - s_{n-1} \times t_{n-1}\right) - \left(s_n - s_{n-1}\right) \times t_{n-1}\\ &= \sum_{i=1}^n \Delta \, \left(s_n \times t_n\right) - \Delta \, s_n \times \left(t_n - \Delta \, t_n\right)\\ &= \Delta^{-1} \, \left(\Delta \, \left(s_n \times t_n\right) - \Delta \, s_n \times t_n + \Delta \, s_n \times \Delta \, t_n\right)\\ &= s_n \times t_n - \Delta^{-1} \, \left(\Delta \, s_n \times t_n\right) + \Delta^{-1} \, \left(\Delta \, s_n \times \Delta \, t_n\right) \end{align*} \]
as demonstrated by deck 3.

Deck 3: Integration By Parts

One of my fellows subsequently suggested that we might have simply exploited the fact that the rule of integration by parts is simply the inverse of the product rule of differentiation, which for sequences we had already figured as
\[ \Delta \, \left(s_n \times t_n\right) = \Delta \, s_n \times t_n + s_n \times \Delta \, t_n - \Delta \, s_n \times \Delta \, t_n \]
and consequently
\[ \begin{align*} \Delta^{-1} \, \left(\Delta \, \left(s_n \times t_n\right)\right) &= \Delta^{-1} \, \left(\Delta \, s_n \times t_n + s_n \times \Delta \, t_n - \Delta \, s_n \times \Delta \, t_n\right)\\ s_n \times t_n &= \Delta^{-1} \, \left(\Delta \, s_n \times t_n\right) + \Delta^{-1} \, \left(s_n \times \Delta \, t_n\right) - \Delta^{-1} \, \left(\Delta \, s_n \times \Delta \, t_n\right)\\ \Delta^{-1} \, \left(s_n \times \Delta \, t_n\right) &= s_n \times t_n - \Delta^{-1} \, \left(\Delta \, s_n \times t_n\right) + \Delta^{-1} \, \left(\Delta \, s_n \times \Delta \, t_n\right) \end{align*} \]
which I must admit is rather more straightforward.

Higher Order Integrals

Finally, we decided to figure a rule for higher order integrals which we can define by repeated integration, much as we did for higher order derivatives. For example
\[ \begin{align*} \Delta^{-1} \, s_n &= \sum_{i=1}^n s_i = \sum_{i=1}^n s_{n+1-i}\\ \Delta^{-2} \, s_n &= \Delta^{-1} \, \left(\Delta^{-1} \, s_n\right) = \sum_{i=1}^n \sum_{j=1}^i s_{i+1-j}\\ &= \left(s_1\right) + \left(s_1+s_2\right) + \left(s_1+s_2+s_3\right) + \dots + \left(s_1+s_2+s_3+\dots+s_n\right)\\ &= \sum_{i=1}^n i \times s_{n+1-i}\\ \Delta^{-3} \, s_n &= \Delta^{-1} \, \left(\Delta^{-2} \, s_n\right) = \sum_{i=1}^n \sum_{j=1}^i j \times s_{i+1-j}\\ &= \left(s_1\right) + \left(2 \times s_1 + s_2\right) + \left(3 \times s_1 + 2 \times s_2 + s_3\right) + \dots\\ &\quad\quad\quad\quad\quad\quad + \left(n \times s_1 + (n-1) \times s_2 + (n-2) \times s_3 + \dots + s_n\right)\\ &= \sum_{i=1}^n s_{n+1-i} \times \sum_{j=1}^i j\\ &= \sum_{i=1}^n \left(\tfrac12 i^2 + \tfrac12 i\right) \times s_{n+1-i} \end{align*} \]
all of which obey the rule
\[ \Delta^{-d}_n \, s_n = \sum_{i=1}^n \Delta^{-(d-2)}_i \, i \times s_{n+1-i} \]
in which we are using the notation \(\Delta^d_c\) to represent the \(d^\mathrm{th}\) order differential operator with respect to \(c\), being a derivative when \(d\) is positive, an integral when it is negative and the identity operator when it is equal to zero, leaving any sequence to which it is applied quite unchanged.
To show that this holds in general we again turned to proof by induction in which we demonstrate that if a proposition holds for the \(n^\mathrm{th}\) case then it must hold for the \((n+1)^\mathrm{th}\) and, consequently, should it hold for the first then it must hold for them all. In particular, we reckoned that given
\[ \begin{align*} t_i &= \Delta^{-(d-2)}_i \, i\\ \Delta^{-(d+1)}_n \, s_n &= \Delta^{-1}_n \, \left(\Delta^{-d}_n \, s_n\right) = \sum_{i=1}^n \sum_{j=1}^i t_j \times s_{i+1-j}\\ k &= i+1-j \end{align*} \]
then since every term from both \(t_1\) to \(t_n\) and \(s_1\) to \(s_n\) contributes to the integral, we must have
\[ 1 \leqslant k \leqslant n\\ 1 \leqslant j \leqslant n \;\implies\;1 \leqslant i+1-k \leqslant n \;\implies\;k \leqslant i \leqslant n-1+k \]
and, since \(i\) can also be no greater than \(n\)
\[ \begin{align*} \Delta^{-(d+1)}_n \, s_n &= \sum_{k=1}^n \sum_{i=k}^n t_{i+1-k} \times s_k = \sum_{k=1}^n s_k \times \sum_{i=k}^n t_{i+1-k}\\ &= \sum_{k=1}^n s_k \times \sum_{i=1}^{n+1-k} t_i = \sum_{k=1}^n s_{n+1-k} \times \sum_{i=1}^k t_i\\ &= \sum_{k=1}^n s_{n+1-k} \times \Delta^{-1}_k \, t_k = \sum_{k=1}^n s_{n+1-k} \times \Delta^{-1}_k \, \left(\Delta^{-(d-2)}_k \, k\right)\\ &= \sum_{k=1}^n s_{n+1-k} \times \Delta^{-(d-1)}_k \, k = \sum_{i=1}^n \Delta^{-((d+1)-2)}_i \, i \times s_{n+1-i} \end{align*} \]
as required.

Of course, we should prefer an explicit formula for \(\Delta^{-d}_i \, i\) and so we figured several values for it in the hope that we might spy some pattern within them
\[ \begin{matrix} i & \Delta_i^1 \, i & \Delta_i^0 \, i & \Delta_i^{-1} \, i & \Delta_i^{-2} \, i & \Delta_i^{-3} \, i & \Delta_i^{-4} \, i & \Delta_i^{-5}\, i\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 2 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 3 & 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 4 & 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 5 & 1 & 5 & 15 & 35 & 70 & 126 & 210 \end{matrix} \]
Clearly this appears to be Pascal's triangle turned upon its side, a fact that in retrospect is quite obvious since
\[ \Delta_i^{-d} \, i = \sum_{j=1}^i \Delta_j^{-(d-1)} \, j = \Delta_i^{-(d-1)} \, i + \sum_{j=1}^{i-1} \Delta_j^{-(d-1)} \, j = \Delta_i^{-(d-1)} \, i + \Delta_{i-1}^{-d} \, (i-1) \]
as compared to the elements of Pascal's triangle which follow the rule
\[ {^n}C_r = {^{n-1}}C_{r-1} + {^{n-1}}C_r \]
Specifically, should we hypothesise that
\[ \Delta_i^{-d} \, i = {^{d+i}}C_{d+1} \]
then
\[ \begin{align*} \Delta_i^{-(d-1)} \, i &= {^{d-1+i}}C_d = {^{d+i-1}}C_d\\ \Delta_{i-1}^{-d} \, (i-1) &= {^{d+i-1}}C_{d+1} \end{align*} \]
and so
\[ {^{d+i}}C_{d+1} = {^{d+i-1}}C_d + {^{d+i-1}}C_{d+1} \implies \Delta_i^{-d} \, i = \Delta_i^{-(d-1)} \, i + \Delta_{i-1}^{-d} \, (i-1) \]
which, in conjunction with the fact that \(\Delta^{-d}_i \, i\) is equal to one whenever \(d\) is equal to minus one or \(i\) is equal to one, is sufficient to prove the hypothesis and we consequently have
\[ \Delta^{-d} \, s_n = \sum_{i=1}^n {^{d+i-2}}C_{d-1} \times s_{n+1-i} = \sum_{i=1}^n {^{d+n-i-1}}C_{d-1} \times s_i \]
as shown by deck 4.

Deck 4: Higher Order Integrals

Having deduced the rules of our sequence calculus, my fellow students and I are keen to explore their consequences but, alas, we shall have to wait until we can take some more time from our studies to do so.
\(\Box\)

References

[1] On A Calculus Of Differences, www.thusspakeak.com, 2017.

[2] You're Going To Have To Think! Why Rational Arithmetic Won't Cure Your Floating Point Blues, www.thusspakeak.com, 2013.

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+