MrMineev

Discrete Calculus

Daniel Mineev

1 Introduction

As you might have already guessed, we deal with discrete functions rather than continuous ones in discrete calculus. A rather peculiar idea comes to mind here: integrating such a function. Let us consider a simple function $f(x) = x$ ; then, in classical calculus, we can easily integrate it from $A$ to $B$ .

∫ b [ 2]b 2 2 xdx = x- = b---a- a 2 a 2

(1)

However, what if we limit the function and accept only integer $x$ ? Then, the integration becomes a summation, which is more complicated.

∑b b(b +1) a(a- 1) i = ---2---- ---2--- i=a

(2)

While some might find the latter simpler to understand, when we consider a more complicated equation, it becomes way harder than anticipated. Consider the function $f(x) = x2$ .

∫ [ ] b 2 x3 b b3---a3 a x dx = 3 a = 3

(3)

b ∑ x2dx = b(b+-1)(2b+-1) - (a---1)a(2a---1)- a 6 6

(4)

The equations look similar. However, the discrete version needs to adjust for all the non-integer values, which makes the equation more complicated. Ironically, it is simpler to calculate an infinite sum of infinitely small segments of a function than to sum a discrete number of values.

Sometimes, it is simpler to prove that a given equation works using induction than to find it. Consider, for example, the following equation.

∑n i = n(n-+-1) i=1 2

(5)

It is quite simple to prove using induction. Let $S n$ be defined as the sum of the first $n$ natural numbers; then we can say the following.

n(n--1)- 2n-+-n(n---1) n(n-+-1)- Sn = n + Sn-1 = n + 2 = 2 = 2

(6)

With a similar method, it is simple to prove that,

∑n i = n(n+-1)(2n+-1) i=1 6

(7)

Again, let $S n$ be the sum of the first $n$ squares, then we can use induction, assuming $S n-1$ is bound by the equation above.

2 6n2 +-n(n--1)(2n--1) 2n3 +-3n2-+n
Sn = n + Sn-1 = 6 = 6 =
n (n + 1)(2n + 1)
= -------6------

(8)

On this note, I will end the light introduction to the topic and start discussing different methods and techniques of discrete integration.

2 Discrete Derivatives

Just like in classical calculus, one must first understand the concept of a derivative before understanding integration. In classical calculus, one would define a derivative in the following way.

f(x +h )- f(x) f′(x) = hli→m0------h-------

(9)

However, in discrete calculus, the smallest step one can make is $h = 1$ . Thus, a discrete version of a derivative will look as follows.

Δf (x) = f(x+ 1)- f(x)

(10)

Usually, instead of saying discrete derivative, it is called the forward difference operator. Consider that; what about higher-order derivates? Then, notice that a second-order derivative would look as follows.

Δ2f(x) = Δ (f(x+ 1)- f(x)) = f(x+ 2)- f(x + 1)- f(x+ 1)+ f(x) =

= f(x + 2)- 2f(x + 1)+ f(x)

(11)

A natural question can arise: how, in general, can one express a $n$ -th order discrete derivative? As we will come to see, a formula does indeed exist.

∑n (n ) Δnf (x) = (- 1)n-i i f (x + i) i=0

(12)

It is quite simple to see if we employ induction. Obviously, the statement is true for $n = 1$ . Let this serve as the base of the induction; now, assume the statement is true for $n$ , then one can prove that it works for $n+ 1$ as follows.

[ ]
n+1 n n∑ n-i(n )
Δ f(x) = Δ (Δ f (x)) = (- 1) i f(x+ 1 +i) -
[ ( ) ] i=0 ( ) ( )
∑n n-i n n n n∑ n-i+1 n
(- 1) i f(x + i) = - (- 1) 0 f(x)+ (- 1) i- 1 f(x+i )-
i=0 n ( ) i=1 ( )
∑ (- 1)n-i n f (x + i) +(- 1)0 n f(x +n + 1)
i=1 i n

(13)

All that is left to simplify the resulting equation is to make use of Pascal’s Identity, $( ) ( ) ( ) ni + ni+1 = n+i+11$ , and get the following.

[ ]
(n ) ∑n (( n ) (n ))
...= - (- 1)n 0 f(x)+ (- 1)n+1-i i- 1 + i f(x +i) +
i=1
0(n) n+∑1 n+1-i(n)
(- 1) n f (x + n+ 1) = (- 1) i f(x+ i)
i=0

(14)

This proves the induction step, and as a result, combined with the base, proves for all $n ∈ ℕ$ .

Seeing the analog of $e$ in Discrete Calculus is interesting. Does there exist such a constant $c$ , such that $Δcx = cx$ ? As it turns out, there does, 2.

Δ2x = 2x+1 - 2x = 2x

(15)

Many properties of classical calculus about derivatives, such as the Product/Quotient Rule, have analogs in discrete calculus. First, the obvious ones,

Δn (f + g)(x) = Δnf (x)+ Δng(x)

Δn (cf(x)) = cΔf (x )

(16)

(17)

Let us now discuss the more interesting one, the Product Rule.

[ ] Δ f(x)g(x) = f(x+ 1)Δg(x)+ g(x)Δf(x)

(18)

The understanding is the same as that of classical calculus; we only got an extra term because terms are not infinitely small, as in classical calculus. Similarly, we have the Discrete Quotient Rule.

[f(x)] g(x )Δf (x)- f(x)Δg(x) Δ g(x) = -----g(x)g(x+-1)------

(19)

And again, this can be proven the exact same way it is proven in classical calculus, with only some minor changes.

3 Fundamental Theorem of Discrete Calculus

Just as in normal calculus, such a thing as a discrete antiderivative exists. As in classical calculus, it is defined similarly.

∑ F (x)dx = f (x) ⇔ Δf (x) = F(x)

(20)

Just as in classical calculus, it is tightly related to discrete integrals through the Fundamental Theorem of Discrete Calculus.

b [ ] ∑ f(x) = ∑ f (x)dx b+1 a a

(21)

This can be proven in the exact same way the fundamental theorem of calculus is proven; I will leave this as an exercise for the reader.

4 Falling Factorial

In classical calculus, there is a very simple formula for calculating an antiderivative of a polynomial, as follows.

∫ (a xn + a xn-1+ ...+ a x+ a )dx = -an-xn+1 + an-1xn+ ...+ a x+ C n n-1 1 0 n+ 1 n 0

(22)

It would be useful to compute the discrete antiderivatives for polynomials as well. However, first, let us introduce some useful terminology. A falling factorial of $n$ is called the following.

(x) = x(x- 1)(x- 2)...(x - n+ 1) = --x!--- n (x - n)!

(23)

Sometimes, it might be called the $n$ -th Pochhammer Polynomial. This function is wonderful because it satisfies the following requirements.

Δ(x)n = n ⋅(x)n- 1

(24)

This can be seen through some trivial calculations.

Δ(x)n = (x + 1)x(x - 1)...(x- n +2) - x (x - 1)(x - 2)...(x- n +1) =
(x +1 - (x - n+ 1))⋅x(x- 1)...(x - n+ 2) = n⋅(x)n-1

This function serves as an analog of exponentiation in Discrete Calculus. Thus, we can easily calculate the derivative/antiderivative of the following polynomial.

P(x) = an (x)n +an- 1(x)n-1 + ...+ a1x + a0
ΔP (x) = nan (x)n-1 +(n - 1)an- 1(x)n-2 + ...+ a1
∑ P(x)dx = -an--(x) + an-1(x) + ...+ a x+ C
n +1 n+1 n n 0

(25)

(26)

(27)

This is almost identical to classical calculus. The only difference is that in usual calculus, one uses exponents, and in discrete calculus, one uses falling factorials. However, it would still be useful to convert a normal polynomial to a falling factorial polynomial, and as luck would have it, indeed, a formula exists. The simplest of which is the following.

Find the dominant coefficient $q$ of the polynomial $S$ .
Subtract from $S$ the value $q(x)n$ , where $n$ is the degree of $S$ .
Go to step one with the updated polynomial $S$ .

In the end, one will get the following system of equations.

(
|| P(x)- qn(x)n = Pn-1(x)
|{ Pn-1(x )- qn- 1(x)n-1 = Pn-2(x )
| ...
||(
P0(x) - q0(x)0 = 0

From which, ones sees that $P (x) = qn(x)n + qn-1(x)n-1 +...+ q0$ . For example, convert $2 x$ into the falling factorial polynomial form.

{
x2 - (x)2 = x2 - x(x - 1) = x

x- (x)1 = 0

From here we see that $2 x = (x )1 +(x)2$ . As an example, this knowledge is already enough to compute the sum of the first cubes $∑n 3 i=1i$ . One must first change the expression into the falling factorial polynomial form from the equation (25).

(| x3 - (x)3 = 3x2 - 2x
||{ 3x2 - 2x- 3(x) = x
2
|||( x- (x)1 = 0

Thus, we see that $x3 = (x)3 + 3(x)2 + (x)1$ . From here, all that is left is to integrate the expression.

∑n 3 [∑ 3 ]n+1 [∑ ( ) ]n+1
x = x dx 1 = (x)3 + 3(x)2 + (x)1 dx
x[=1 ] 1
(x)4- (x)2 n+1 (n+-1)n(n--1)(n---2)
= 4 + (x)3+ 2 +C 1 = 4 + (n+1 )n(n- 1)(n- 2)
( )2
+ (n-+-1)n= n(n-+1)-
2 2

(28)

Thus, now one can see that,

∑n (n (n + 1))2 x3 = ----2--- x=1

(29)

With the same technique, discrete integrals of any polynomial can be found, even more than we originally hoped.

5 Conclusion

Generally speaking, the topic of discrete calculus has a lot of connections with stirring numbers; for example, the following holds true:

m { } xm = ∑ m (x)k k=0 k

(30)

This can be used to prove various identities with falling factorials. Specifically, this relation shows us that instead of the tedious method described earlier for expressing a polynomial using a Pochhammer polynomial, it is important to note that in practice if one does not have access to machine calculations, the method described before is better. I will not explain this in this article; I will leave this for another time.

I hope that you have found the given material interesting and useful. Discrete Calculus is quite an exotic and fascinating topic in mathematics.

1 Introduction
2 Discrete Derivatives
3 Fundamental Theorem of Discrete Calculus
4 Falling Factorial
5 Conclusion