Discrete Integral?

Inspired by this quiz about discrete derivatives.

When I found this quiz, I remembered a thought I had had when I had heard about the formula k=1nk=n(n+1)2 \sum_{k=1}^n k = \frac{n(n+1)}2 .

If you expand the fraction, you get 12n2+12n \frac 1 2 n^2 + \frac 1 2 n , which almost looks like the antiderivative of k k except for the 12n \frac 1 2 n term. When I did this for other sums, I got the same result:

k=1nk2=13n3+12n2+16n \sum_{k=1}^n {\color{#D61F06} k^2} = {\color{#D61F06} \frac 1 3 n^3} + \frac 1 2 n^2 + \frac 1 6 n

k=1nk3=14n4+12n3+14n2 \sum_{k=1}^n {\color{#D61F06} k^3} = {\color{#D61F06} \frac 1 4 n^4} + \frac 1 2 n^3 + \frac 1 4 n^2

k=1nk4=15n5+12n4+13n3130n \sum_{k=1}^n {\color{#D61F06} k^4} = {\color{#D61F06} \frac 1 5 n^5} + \frac 1 2 n^4 + \frac 1 3 n^3 - \frac 1 {30} n

...

Because of the definition of these sums, their discrete derivatives are always na n^a (a is some natural number), but even for discrete derivatives of simple polynomials the fundametal theorem of calculus still almost holds; at least for the highest order term.

So now I'm wondering if

  1. this also holds for functions that aren't polynomials, for example exponential functions or trigonometric functions
  2. the discrete antiderivative of the discrete antiderivative is also similar to the normal second antiderivative
  3. there are some polynomials for which antiderivative and discrete antiderivative are exactly the same

EDIT: I've found the thing I'm calling "discrete antiderivative" as finite difference on Wikipedia and the article points out Faulhaber's formulas and the difference between odd and even degree polynomials. However, I haven't found what I'm searching for – a comparison/link to standard calculus integrals.

#Combinatorics

Note by Henry U
2 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

The formulas you have provided are called Faulhaber's formulas and are linked to Bernoulli numbers. There is a result by John Conway recently (2016, I think), where he is able to compute "derivatives" and "integrals" of these Faulhaber formulas, which distinguish between odd degrees and even degrees of the polynomials. Note that here, the notions of "derivative" and "integral" are merely just linear functions on polynomials in nn, which sends one polynomial to another with the linearity properties satisfied; no notion of calculus is required here. Because of this, we need to be precise as to what a "derivative" and an "integral" is here, as well as what a "discrete derivative" and a "discrete antiderivative" here. None of your questions can be answered without first establishing this point; you cannot simply input the framework of calculus into something that is only applied in a discrete way.

P.S. As for "exponential" functions and "trigonometric" functions, I don't see the relevance of Faulhaber's results to them as they are not properly defined currently.

A Former Brilliant Member - 2 years, 8 months ago

Log in to reply

I would say,

  1. Derivative and Antiderivative are defined by the power rule from calculus, so nothing discrete here
  2. The discrete derivative is defined as f(x+1)f(x) f(x+1)-f(x) – just like in the quiz.
  3. The discrete integral is defined by Faulhaber's formula – thank you for pointing that out – as k=1nka \sum_{k=1}^n k^a

Then all those four functions applied to polynomials are also polynomials and satisfy linearity (because of the commutative property for 2. and the linearity of sums for 3.)

So with these definitions, I hope I have stated my questions unambiguously, but I also think that they don't really make sense for other functions like exponential or trigonometric functions. But Conway's result sounds interesting, I think I'll take a look at it.

Henry U - 2 years, 8 months ago

Log in to reply

What power rule from calculus? It's simplest to just define the Derivative as a linear map, where for integers n1 n \geq 1 ,

D(xn)nxn1 D(x^n) \equiv nx^{n-1}

and the Integral as the inverse mapping of the Derivative, i.e. for integers n0 n \geq 0 ,

I(xn)D1(xn)=xn+1n+1. I(x^n) \equiv D^{-1}(x^n) = \frac{x^{n+1}}{n+1}.

This was how Conway presented his definitions; with this, you don't need to be sloppy with them and avoids having to define a "discrete" version of them. As I said, no notion of calculus is ever involved; we are merely defining the Derivative and Integral as linear maps/functions which map one polynomial to another.

My main point was to ask you why you care to link these to the "standard" framework of calculus, when we have a nice stand-alone framework to study Faulhaber polynomials which only involve algebra & combinatorics.

P.S. I urge you again to look up Bernoulli numbers; I think this should answer your question regarding the coefficient of the largest-degree term.

A Former Brilliant Member - 2 years, 8 months ago

Log in to reply

@A Former Brilliant Member My main reason to link these to calculus was because I am more familiar with (anti-)derivatives and I thought they don't look as complicated (The antiderivative of some polynomial involves only one term for each term of the polynomial whereas Faulhaber's formula has many more terms of lower degree).

And then I also thought, if we have one mapping I(xn)=D1(xn)=xn+1n+1 I(x^n) = D^{-1}(x^n) = \frac{x^{n+1}}{n+1} and then another mapping F(xn)=(Faulhabersformula) F(x^n) = (Faulhaber's formula) , of course it will be interesting if there exist polynomials for which these two mappings give the same result.

Henry U - 2 years, 8 months ago

Log in to reply

@Henry U I understand, but you must let go of the standard calculus framework when you venture into the world of discrete mathematics, as nothing from there will work out well. One clarification: Faulhaber's formula is a polynomial, and hence cannot be considered a mapping.

As to your final sentence, I vehemently disagree; there is no polynomial that is invariant under the Derivative or Integral linear map (it is easy to show this). You will have to venture into the realm of fiction to find such a case, by relying on "infinite processes" which would go against everything in discrete mathematics.

EDIT: To save you the trouble, note that what you would call "exponential" or "trigonometric" functions are really just "infinite sums".

A Former Brilliant Member - 2 years, 8 months ago

Log in to reply

@A Former Brilliant Member Could you maybe describe a little proof why there exists no polynomial p(x) p(x) for which I(p(x))=F(p(x)) I(p(x)) = F(p(x)) is true?

I don't directly see an intuitive reason why this is true, but I also haven't found an example.

Henry U - 2 years, 8 months ago

Log in to reply

@Henry U (I thought I replied to this already... hmm.)

I think you are asking the wrong questions. Did you read up on Faulhaber polynomials? They simply give the sum of the kthk^{\text{th}} powers of the first nn numbers... so it does not make sense to talk about the Faulhaber polynomial of a polynomial.

I firmly believe you are trying to muddy the waters between the standard framework of calculus and what one would call "discrete calculus", which relies more on difference equations than limiting processes. The two areas, while not mutually exclusive, are highly divergent from one another and thus it's important to separate both frameworks.

A Former Brilliant Member - 2 years, 7 months ago

Log in to reply

@A Former Brilliant Member By the faulhaber polynomial of a polynomial, I meant the sum of the faulhaber polynomials of the terms of the polynomial (too complicated). For exapmle,

p(n)=n22n p(n)=n^2-2n

Of course

F(n2)=13n3+12n2+16n F(n^2) = \frac 1 3 n^3 + \frac 1 2 n^2 + \frac 1 6 n

and

F(n)=12n2+12n F(n) = \frac 1 2 n^2 + \frac 1 2 n

Now I thougut, every polynomial (like p(n) p(n) ) is a linear combination of all powers of n n . So the Faulhaber polynomial could be the same linear combination of the individual Faulhaber polynomials.

F(n22n)=F(n2)2F(n) F(n^2-2n) = F(n^2) - 2F(n)

This makes sense because F(na) F(n^a) is just a partial sum of na n^a and, since sums are linear, we can split one sum of a polynomial into many sums, one for each term of the polynomial.

In my example, I would argue

F(n22n)=F(n2)2F(n)=(13n3+12n2+16n)2(12n2+12n)=13n312n256n F(n^2-2n) = F(n^2) - 2F(n) = (\frac 1 3 n^3 + \frac 1 2 n^2 + \frac 1 6 n) - 2(\frac 1 2 n^2 + \frac 1 2 n) = \frac 1 3 n^3 - \frac 1 2 n^2 - \frac 5 6 n

Henry U - 2 years, 7 months ago

Log in to reply

@Henry U But it’s not a linear mapping...

A Former Brilliant Member - 2 years, 7 months ago

Log in to reply

@A Former Brilliant Member I think it is. If you double the left side, you have 2F(n22n) 2F(n^2-2n) and I think this is equal to t he right side with doubled coefficients. Or isn't that the definition of linear?

Henry U - 2 years, 7 months ago

Log in to reply

@Henry U I think you need to revisit the definition of a linear mapping... in any case, you are overcomplicating your problem & question. Go five steps back and take a deep breath.

A Former Brilliant Member - 2 years, 7 months ago

Log in to reply

@A Former Brilliant Member I'm haven't any experience with vector spaces, but I think I understand what a linear mapping is, at least well enough to say why faulhaber's formula is a linear mapping. Here's what I think:

Wikipeda says

[…] A linear map […] is a mapping VW V \to W between two modules (including vector spaces) that preserves (in the sense defined below) the operations of addition and scalar multiplication.

Let V V and W W be vector spaces over the same field K \mathbf{K} . A function f:VW f : V \to W is said to be a linear map if for any two vectors u,vV \mathbf {u} ,\mathbf{v} \in V and any scalar cK c \in \mathbf{K} the following two conditions are satisfied:
f(u+v)=f(u)+f(v) f(\mathbf{u}+\mathbf{v}) = f(\mathbf{u})+f(\mathbf{v})
f(cu)=cf(u f(c\mathbf{u}) = c f(\mathbf{u}

  • Applying Faulhaber's formula to a polynomial is a mapping between two vector spaces since the set of polynomials is a (infinitely-dimensional) vector space
  • Faulhaber's formula gives thhe result of a summation, which is linear, so the formula is also linear

Henry U - 2 years, 7 months ago

@A Former Brilliant Member But of course, Discrete Mathematics and calculus don't really fit together, so maybe this won't lead to anything

Henry U - 2 years, 7 months ago
×

Problem Loading...

Note Loading...

Set Loading...