Post Reply 
"Counting in their heads" - 1895 oil painting
08-12-2020, 01:50 PM (This post was last modified: 08-15-2020 07:26 PM by Albert Chan.)
Post: #21
RE: "Counting in their heads" - 1895 oil painting
There is also a pattern for sp (see Benoulli Number thread)

\(s_p(n) = \sum_{x=0}^{n-1}x^p = \large {n^{p+1}\over p+1} - {n^p \over 2}
+ {p\over12}(n^{p-1}) + k_{p-3}(n^{p-3}) + k_{p-5}(n^{p-5}) + \cdots \)

sp(1) = sp(0) + 0^p = sp(0) = 0

⇒ above formula does not have a constant term
⇒ when p is odd, p>1, sp(n) has factor n²

Redo previous example:

s5(n) = n^6/6 - n^5/2 + 5/12*n^4 + k2*n^2
s5(1) = 1/6 - 1/2 + 5/12 + k2 = 0

→ k2 = -1/12
→ s5(n) = (2*n^6 - 6*n^5 + 5*n^4 - n^2) / 12

T = 50^5 + 51^5 + 52^5 + ... + 150^5
   = s5(151) - s5(50)
   = 1936617185625 - 2450520625
   = 1934166665000

Update: we may use this to help mental calculation: For n ≥ 0, sp(n) = (-1)p+1 * sp(1-n)

Redo above example, using s5(151) = s5(-150), and horner's rule
Code:
b = -150
a = 50
d = b-a = -200
d2 = (b^2-a^2)/d = b+a      = -100 
d3 = (b^3-a^3)/d = d2*b+a^2 =  17500
d4 = (b^4-a^4)/d = d3*b+a^3 = -2500000
d5 = (b^5-a^5)/d = d4*b+a^4 =  381250000
d6 = (b^6-a^6)/d = d5*b+a^5 = -56875000000

T = s5(b) - s5(a) = (2*d6 - 6*d5 + 5*d4 - d2)*d / 12 = 1934166665000

Update: we are better off using Euler-Maclaurin formula, which work for any f(x)
Note: coefficients were B(1)/1! = -1/2, B(2)/2! = 1/12, B(4)/4! = -1/720, ...

Σf = Δ-1 f = (eD-1)-1 f = (D-1 - 1/2 + D/12 - D³/720 + ...) f

Example, with f = x^5

s5 = ∫f dx - f/2 + f'/12 - f'''/720 + ... = x^6/6 - x^5/2 + (5x^4)/12 - (60x^2)/720
Find all posts by this user
Quote this message in a reply
08-13-2020, 03:50 PM
Post: #22
RE: "Counting in their heads" - 1895 oil painting
There is also the Faulhaber polynomials, with sum-of-powers formula as function of triangular number.

Let \(\large t = \binom{x}{2},\;{s_{2m} \over (2x-1)t}\) and \(\large {s_{2m+1} \over t^2}\) are polynomial of t, degree m-1

Example, get s4(x) and s5(x) in terms of t, using divided difference.
Note: we start from x=2, instead of 0, to avoid divide-by-zero issue.

Code:
x   s4(x)    | t    s4/(2xt-t)  divided-diff
2   0+1^4=1  | 1    1/3
3   1+2^4=17 | 3    17/15       (17/15-1/3)/(3-1) = 2/5

--> s4(x) = (2xt-t) * (1/3 + (t-1)*2/5) = (2x-1)*(6t^2-t)/15

x   s5(x)    | t    s5/t^2      divided-diff
2   0+1^5=1  | 1    1
3   1+2^5=33 | 3    11/3        (11/3-1)/(3-1) = 4/3

--> s5(x) = t^2 * (1 + (t-1)*4/3) = (4t^3-t^2)/3

Redo previous example, using horners rule for the difference.

Code:
lua> a,b = 50, 151      -- next line replaced with t's
lua> a,b = a*(a-1)/2, b*(b-1)/2
lua> d = b-a            -- = 10100
lua> d2 = b+a           -- = (b^2-a^2)/d = 12550
lua> d3 = d2*b+a^2      -- = (b^3-a^3)/d = 143629375
lua> (4*d3 - d2)*d / 3  -- = 50^5 + 51^5 + ... + 150^5
1934166665000
Find all posts by this user
Quote this message in a reply
08-14-2020, 02:25 PM (This post was last modified: 08-14-2020 02:29 PM by Albert Chan.)
Post: #23
RE: "Counting in their heads" - 1895 oil painting
(08-12-2020 01:32 AM)Albert Chan Wrote:  I was wrong. There seems to be a pattern to sum of powers formula after all ...

\( S_p = n c^p + \large {n^3-n \over 12} \left(
\binom{p}{2} c^{p-2} +
{3n^2-7 \over 20} \binom{p}{4} c^{p-4} +
{3n^4-18n^2+31 \over 112} \binom{p}{6} c^{p-6} +
{5n^6-55n^4+239n^2-381 \over 960} \binom{p}{8} c^{p-8} +
\cdots \right) \)

Example:

50^5 + 51^5 + 52^5 + ... + 150^5              // p=5, c=100, n=101

= 101*100^5 + 102*101*100/12 * (10*100^3 + (3*101^2-7)/20*5*100)
= 1934166665000

To extend formula for spacings = d, simply replace Sp by Sp/dp, c by c/d
Or, just check the dimensions for each term. All terms must have same units.

Example, for sum-of-squares, all terms should have unit of c²

S2 = n*c² + (n³-n)/12 *         // c/d is dimensionless, thus c, d have same unit

Example, for sum of m odd squares

1² + 3² + 5² + ... + (2m-1)²       // d=2, c = m = n
= m*m² + m*(m²-1)/12 * 2²
= m*(4m²-1)/3
= \(\binom{2m+1}{3}\)

We can confirm this from sum-of-n-squares formula

\(\begin{align}
{n(n+1)(2n+1) \over 6} &= {n(n+1)·[(n-1) + (n+2)] \over 6}\\
\binom{2n+2}{3}/4 &= \binom{n+1}{3} + \binom{n+2}{3}\\
\end{align}\)

Let n = 2m:
LHS = sum-of-m-odd-squares + sum-of-m-even-squares
\(\binom{n+2}{3}\) = 4×sum-of-m-squares = sum-of-m-even-squares

⇒ \(\binom{2m+1}{3}\) = sum-of-m-odd-squares
Find all posts by this user
Quote this message in a reply
08-14-2020, 07:20 PM
Post: #24
RE: "Counting in their heads" - 1895 oil painting
C'mon now Albert... Is all this really 'in your head'? Seems like many whiteboards...

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
08-15-2020, 02:55 AM
Post: #25
RE: "Counting in their heads" - 1895 oil painting
(08-13-2020 03:50 PM)Albert Chan Wrote:  There is also the Faulhaber polynomials, with sum-of-powers formula as function of triangular number.

Let \(\large t = \binom{x}{2},\;{s_{2m} \over (2x-1)t}\) and \(\large {s_{2m+1} \over t^2}\) are polynomial of t, degree m-1

...

Redo previous example, using horners rule for the difference.

Code:
lua> a,b = 50, 151      -- next line replaced with t's
lua> a,b = a*(a-1)/2, b*(b-1)/2
lua> d = b-a            -- = 10100
lua> d2 = b+a           -- = (b^2-a^2)/d = 12550
lua> d3 = d2*b+a^2      -- = (b^3-a^3)/d = 143629375
lua> (4*d3 - d2)*d / 3  -- = 50^5 + 51^5 + ... + 150^5
1934166665000

Indeed there is more than a way to skin a cat (if we still may say that these days).
There is also Hurwitz zeta function.

For example,

ζ(-5, 50) - ζ(-5, 151) = 1934166665000

But what calculator has that built-in?
Find all posts by this user
Quote this message in a reply
08-15-2020, 05:04 AM
Post: #26
RE: "Counting in their heads" - 1895 oil painting
(08-15-2020 02:55 AM)Gerson W. Barbosa Wrote:  There is also Hurwitz zeta function.

For example,

ζ(-5, 50) - ζ(-5, 151) = 1934166665000

But what calculator has that built-in?

Anybody know which zeta function Prime's CAS uses when Zeta() is given two arguments? Prime evaluates Zeta(2,2) as 1.9892802343, but Wolfram Alpha returns pi^2/6-1 (approx 0.644934) for HurwitzZeta(2,2). Prime's Help screen for Zeta() does not mention a two-argument syntax, so it's a mystery to me.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
08-15-2020, 07:20 AM
Post: #27
RE: "Counting in their heads" - 1895 oil painting
(08-15-2020 05:04 AM)Joe Horn Wrote:  Anybody know which zeta function Prime's CAS uses when Zeta() is given two arguments?

That’s the derivative of Zeta function. The second argument is the derivative order. In W|A:

(d^2 ζ(x))/(dx^2), x = 2
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: