Have you ever wanted to know why \sum_{i=0}^{n} i = n(n+1)/2? The obvious proof is by induction, but it doesn't give us insight as to how we got the formula. I'll show you how to derive these formulas using discrete calculus.
We can actually derive this solution for any sum of powers using discrete calculus. We need a few things:
The falling factorial
The discrete derivative
The discrete integral
The falling factorial is pretty straightforward. We denote it as follows: x^{n} = x(x1)(x2) ... (x  (n1)).
So n^{3} = n(n1)(n2).
We now want a discrete derivative. In regular calculus, we have our difference quotient: lim_{x \to a} [f(x)  f(a)]/(x  a). In discrete calculus, we're dealing with integers, not reals. So our difference is 1. We have: Df(x) = f(x + 1)  f(x).
So now the interesting part is that Dx^{n} = nx^{n1}.
And of course, our discrete integral is a sum which reflects the correlation to integration of a polynomial power in continuous calculus: Integral( x^{n} ) = x^{n+1}/(n+1) (in the continuous case).
In the discrete case, we get that \sum_{x=a}^{b1} x^{i} = (b^{i+1}  a^{i+1})/(i+1).
So for example, the discrete integral of x^{2} from 0 to 5 is x^{3}/3 = x(x1)(x2)/3 = 5 * 4 * 3/3 = 20.
Now, let's put it all together. The trick is to write the power in terms of falling factorials. So:
x = x^{1}
x^{2} = x^{2} + x^{1} = x(x1) + x
We then take a discrete integral and do some algebra. So for your case of \sum_{i=0}^{n} i = (n+1)^{2}/2 = n(n+1)/2.
If we consider the case of \sum_{i=0}^{n} i^{2} = \sum_{i=0}^{n} (i^{2} + i) = i(i+1)(i1)/3 + (i+1)i/2. Doing some algebra gets us n(n+1)(2n+2)/6 as the answer for the summation.
There is actually a closed form solution using Stirling Numbers of the Second Kind to rewrite x^{n} in terms of sums of falling factorials. I will use S(n, k) to denote Stirling Numbers of the Second Kind.
I note S(n + 1, k) = k * S(n, k) + S(n, k1), with S(0, 0) = 1 and S(0, n) = S(n, 0) = 0. There is also an explicit formula for Stirling Numbers of the Second Kind, provided on the Wikipedia link.
So x^{n} = \sum_{i=0}^{n} S(n, k) x^{k}. (Note that if the x in the summation isn't being parsed correctly. It should be a falling factorial [il]x^{[u]k}).
Thus, we can derive a closedform solution for any sum of powers, giving us an Theta(1) solution as opposed to Theta(n).
We can actually derive this solution for any sum of powers using discrete calculus. We need a few things:
The falling factorial
The discrete derivative
The discrete integral
The falling factorial is pretty straightforward. We denote it as follows: x^{n} = x(x1)(x2) ... (x  (n1)).
So n^{3} = n(n1)(n2).
We now want a discrete derivative. In regular calculus, we have our difference quotient: lim_{x \to a} [f(x)  f(a)]/(x  a). In discrete calculus, we're dealing with integers, not reals. So our difference is 1. We have: Df(x) = f(x + 1)  f(x).
So now the interesting part is that Dx^{n} = nx^{n1}.
And of course, our discrete integral is a sum which reflects the correlation to integration of a polynomial power in continuous calculus: Integral( x^{n} ) = x^{n+1}/(n+1) (in the continuous case).
In the discrete case, we get that \sum_{x=a}^{b1} x^{i} = (b^{i+1}  a^{i+1})/(i+1).
So for example, the discrete integral of x^{2} from 0 to 5 is x^{3}/3 = x(x1)(x2)/3 = 5 * 4 * 3/3 = 20.
Now, let's put it all together. The trick is to write the power in terms of falling factorials. So:
x = x^{1}
x^{2} = x^{2} + x^{1} = x(x1) + x
We then take a discrete integral and do some algebra. So for your case of \sum_{i=0}^{n} i = (n+1)^{2}/2 = n(n+1)/2.
If we consider the case of \sum_{i=0}^{n} i^{2} = \sum_{i=0}^{n} (i^{2} + i) = i(i+1)(i1)/3 + (i+1)i/2. Doing some algebra gets us n(n+1)(2n+2)/6 as the answer for the summation.
There is actually a closed form solution using Stirling Numbers of the Second Kind to rewrite x^{n} in terms of sums of falling factorials. I will use S(n, k) to denote Stirling Numbers of the Second Kind.
I note S(n + 1, k) = k * S(n, k) + S(n, k1), with S(0, 0) = 1 and S(0, n) = S(n, 0) = 0. There is also an explicit formula for Stirling Numbers of the Second Kind, provided on the Wikipedia link.
So x^{n} = \sum_{i=0}^{n} S(n, k) x^{k}. (Note that if the x in the summation isn't being parsed correctly. It should be a falling factorial [il]x^{[u]k}).
Thus, we can derive a closedform solution for any sum of powers, giving us an Theta(1) solution as opposed to Theta(n).
0 Comments On This Entry
← January 2020 →
S  M  T  W  T  F  S 

1  2  3  4  
5  6  7  8  9  10  11 
12  13  14  15  16  17  18 
19  20  21  22  23  24  25 
26  27  28  29  30  31 
My Blog Links
Recent Entries

Discrete Calculus and Sums of Powers
on Aug 03 2014 09:20 PM
Recent Comments
Search My Blog
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)