Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the context of discrete calculus, or calculus of finite differences, is there a theorem like the chain rule that can express the finite forward difference of a composition $∆(f\circ g)$ in simplified or otherwise helpful terms?

It's probably not possible for a general function, but it might be possible with some restrictions. I'm also interested in the reverse -- a substitution rule for indefinite sums, if such exists. Or, to be honest, in any strong wealth of technical information related to this topic.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Provided the values of $g$ lie in the domain of $f$ and $\Delta g(n)$ is an integer, you have the obvious rule $$ \Delta(f\circ g)(n)=\sum_{d=0}^{\Delta g(n)-1}\Delta f\bigl(g(n)+d\bigr), $$ where the summation must be interpreted as a sum of negated terms in case $\Delta g(n)<0$, similarly to integrals whose upper limit is lower than their lower limit. The formula is probably not very useful though.

Added: I just found out that for such summations that might go in the wrong direction, the book Concrete Mathematics uses the notation $$ \Delta(f\circ g)(n)=\sum\nolimits_0^{\Delta g(n)}\Delta f\bigl(g(n)+i\bigr)\,\delta i $$ (the factor $\delta i$ is always $1$, but serves to indicate the sum is over $i$; also the upper bound, here $\Delta g(n)$, is omitted from the range of $i$) to emphasize even more the analogy with an integral.

share|improve this answer
I think I might not understand your formula properly. How can you do this if $∆g$ is not constant? You would need to perform the summation on the arbitrary points $Δg(0),Δg(1),...$. –  Greg Ros Nov 12 '12 at 15:27
@anon Yes, I wrote the right parenthesis in the wrong place; corrected now. Thank you! –  Marc van Leeuwen Nov 12 '12 at 18:16
Ah I'm sorry, I misunderstood the intent at first. I understand. –  Greg Ros Nov 12 '12 at 18:20
Thanks! I'm sorry for the misunderstanding at first. You can actually make the sum from $g(n)$ to $g(n+1)$, or to $g(n)+Δg$, thus removing the inner function from the sum itself. Unfortunately, I'm not sure how to simplify it. It just evaluates back to $f(g(n)+Δg)-f \circ g(n)$, since Δf is going to just become f anyway. I've played around with a similar notion that also applies if Δg is not an integer; to a derivative and an integral. However, it all just ends up being similar to the normal formula. –  Greg Ros Nov 12 '12 at 18:42
add comment

While I doubt I'll ever find any general formulas, I've noticed that you can derive such a formula from many functions. For example, for $sin(x)$ we have: $$\sin{f(x)}⇒Δ\big({\sin{f(x)}}\big)=\sin{f(x+1)}-\sin{f(x)}=\sin{\big(f(x) + Δf(x)\big)}-\sin{f(x)}=$$ Using a trig identity: $$\sin{\big(\frac{1}{2}Δf(x)\big)}·\cos{\big(f(x)+\frac{1}{2}∆f(x) \big)}$$ For $2^{x}$, the discrete analog to $e^{x}$: $$Δ2^{f(x)}=2^{f(x)+Δf(x)}-2^{f(x)}=2^{f(x)}(2^{∆f(x)}-1)$$

While there is no chain rule to work with in discrete calculus, it seems that finding the differences (and hence, the discrete integrals) is somewhat easier.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.