[Edu-sig] Exploring Bernoulli Numbers
Kirby Urner
pdx4d@teleport.com
Fri, 19 Jan 2001 00:56:29 -0800
More of the usual math-through-programming jazz.
A continuation of a thread on math-teach at the
Math Forum...
Kirby
=====================================================
>We see that the number of subtriangles in each row = 2n - 1
>(series of odds, n = 1,2,3...) and that the n+1 row will
>duplicate the previous, plus add 2 more triangles i.e.
>
> row(n+1) = (2n - 1) + 2 = 2n + 1
> ^^^^^^^^ ^
> triangles 2
> in last row more
>
>See: http://www.inetarena.com/~pdx4d/ocn/graphics/triarea.gif
Of course this is a good visual proof that n^2 (n=1,2,3...)
is the sum of the first n consecutive odd numbers, i.e.
n
n^2 = SIGMA (2n-1)
i=1
Kids lucky enough to have a CLI can write:
>>> def odd(n): return 2*n - 1
>>> import operator
>>> def g(f,n):
"""
n
g(f,n) = SIGMA f(i)
i=1
"""
return reduce(operator.add,map(f,range(1,n+1)))
>>> g(odd,5)
25
and so on.
This brings me to another beef I have with the way K-16
math is usually taught: we make the silly rule that if the
students can't actually do the math that might be relevant
in a given thread, then we probably shouldn't even talk
about it.
What other subjects do we teach according to this rule.
Don't listen to Bach until you can play like Bach, don't
read Shakespeare until you can write like Shakespeare --
ridiculous. And yet text books are careful to just coast
along at the level of "exercises", where the students are
supposed to do, do, do.
Whatever happened to kicking back and appreciating the
masters, getting a sense of what high quality mathematics
is like without actually trying to be a master yourself?
That's how we do it most music and art and literature.
For some reason, math is supposed to be different. Why?
For example, here we are talking about sums of 2nd power
expressions expressible as a 3rd power equation (tetrahedral
and cuboctahedral numbers), or 2nd powers = sums of 1st
powers (e.g. sum of consecutive odds, or consecutive
integers).
There's the theme of degree, and of consecutive integers
(plus the linear, areal, volume relationship for powers
1,2,3). What other mathematics is relevant in this
connection?
A student tracking this thread might ask, or, if told,
might appreciate, that people asked themselves long ago
whether the sum of consecutive integers to the 5th power
might be expressed as a polynomial to the 6th power, or
whether 1^7 + 2^7 + 3^7 +... + (n-1)^7 + n^7 might be
equivalent to some polynomial in the form A[1] n^8 +
A[2] n^7 + A[3] n^6 + ... + A[n] n, where A[1]... A[n]
are rational coefficients. In general, given:
n
SIGMA f(i) where f(i) = i^x
i=1
we want to find a corresponding:
n+1
SIGMA A(i) n^i A(1)..A(n) = rational numbers
i=1
that gives the same result.
Just to be able to understand the problem, to appreciate
what's being sought, is mental exercise enough at some
levels. You don't have to expect kids to then sit down
and pull the Bernoulli numbers out of a hat (the Bernoullis
figure in to the computation of these coefficients, which
are also functions of x -- see below).
What's being exercised here is a kind of math literacy.
We have SIGMAs flying around, and an exponent that's also
a variable. It's like trying to decipher some code, to
make sense of the terrain. Even before proofs, or
derivations, you just need to practice with the lingo.
It probably helps in many cases to write the top SIGMA
as a simple program at the CLI:
>>> def sumpow(n,x):
sum = 0
for i in range(1,n+1):
sum = sum + i**x
return sum
>>> sumpow(5,5)
4425
>>> 1**5 + 2**5 + 3**5 + 4**5 + 5**5
4425
This is a departure from my usual approach of defining f(i)
and SIGMA and composing them as g(f,n). That's OK. We
should do it both ways.
One reason I like hyperlinking to the Bernoulli numbers
at this point because here's where we hook in Ada, the
Countess Lovelace. We have few enough women in the
narrative, but Ada makes up for a lot of what's missing.
She's a perfect character to include for young students:
Five weeks after Ada was born Lady Byron asked for
a separation from Lord Byron, and was awarded sole
custody of Ada who she brought up to be a mathematician
and scientist. Lady Byron was terrified that Ada might
end up being a poet like her father. Despite Lady
Byron's programming Ada did not sublimate her poetical
inclinations. She hoped to be "an analyst and a
metaphysician". In her 30's she wrote her mother, if
you can't give me poetry, can't you give me "poetical
science?" Her understanding of mathematics was laced
with imagination, and described in metaphors
And here's the link to Bernoulli numbers:
When inspired Ada could be very focused and a
mathematical taskmaster. Ada suggested to Babbage
writing a plan for how the engine might calculate
Bernoulli numbers. This plan, is now regarded as
the first "computer program." A software language
developed by the U.S. Department of Defense was
named "Ada" in her honor in 1979.
[ http://www.well.com/user/adatoole/bio.htm ]
Of course critics will say the above narrative means
Ada is a heroine in computer world, and her name has
no relevance to math classes -- nevermind about the
Bernoullis or that "computer science" wasn't even
invented as a discipline yet (in those days, you weren't
considered "interdisciplinary" just because you thought
about computing machinery in connection with computing).
Again, I think in K-12 at least, there's no need to
carve learning into math without much programming on
the one hand, and programming without much math on the
other -- they synergize so well, that they deserve to
be fused more deeply. Convergence is a trend, or
should be a trend. It's a symptom of overspecialization
that so many schools have fancy computer labs, but in
math class kids have to make do with calculators.
Back to Python, kids can import, and play with the
Bernoullis. As rational numbers, they may be expressed
as (numerator, denominator) pairs. Here's real.py
in action (slightly tweeked by me to fin Python 2.0
syntax), a powerful, jewel of a module by Jurjen N.E. Bos:
>>> from real import *
>>> map(bern,range(0,20))
[(1L, 1L), (-1, 2), (1L, 6L), (0, 1), (-1L, 30L),
(0, 1), (1L, 42L), (0, 1), (-1L, 30L), (0, 1),
(5L, 66L), (0, 1), (-691L, 2730L), (0, 1),
(7L, 6L), (0, 1), (-3617L, 510L), (0, 1),
(43867L, 798L), (0, 1)]
... which is to say that B(i) is 0 for all odds except
B(1), and B(2) = 1/6, B(4) = -1/30 B(6) = 1/42, B(8) =
-1/30 and so on. The "L"s you see in the above tuples
stand for "long": these are what we call BigNumbers, e.g.:
>>> bern(200)
(-498384049428333414764928632140399662108495887
4572066749680558226172636696215236875688658023
0221099913260141269761327939105865452714534051
5840099290478026350382802884371712359337984274
122861159800280019110197888555893671151L,
1366530L)
We don't have our coefficients yet, but there's light at
the end of the tunnel at last.
For my coefficients, I turn to Chapter 20, The Bernoulli Era,
in 'The History of Mathematics' by Carl Boyer (2nd edition,
John Wiley and Sons, 1991), pg. 419. Again, this isn't
something I can necessarily derive on my own, not being a
mathematician of Jacques Bernoulli's caliber (I might be
able to follow a proof -- none given in this context).
But does this mean such math is uninteresting to me, or
that I shouldn't be exposed to it? No way. Nor should
my students be so insulated.
"Math appreciation" means being able to follow what others
have done _without_ making the claim that you could or
should be able to do the same. We need to take away the
notion that the only math worth reading, playing with,
exploring, is math you have the capacity or ability to
reinvent yourself, from scratch, ab initio.
That doesn't mean we should teach mindless rule-following
without comprehension at every turn. But it does mean
there should be phases of study in which we're testing
and verifying, applying and trying out -- because these
activities also involve a level of comprehension and
exercise. Math is a communal activity. No single human
could reinvent it all, not even Gauss. That's life in
the real world.
For example I, or my student, can translate the mathematical
notation provided by Boyer into executable, and therefore
testable code. I've done this in my bernoulli.py, which
contains coeffs(), a method for returning the sought-for
coefficients -- for which the Bernoulli numbers were needed:
from real import bern
def coeffs(x):
A = [(1,x+1),(1,2)]
if x<2: return A
num,den,k = x,2,2
while x>1:
b = bern(k)
A.append((num*b[0],den*b[1]))
num = num*(x-1)*(x-2)
den = den*(k+1)*(k+2)
k = k+2
x = x-2
return A
If I'm summing numbers to the 1st power, what are my
coefficients?
>>> bernoulli.coeffs(1)
[(1, 2), (1, 2)]
i.e.
n
SIGMA n = (1/2)n^2 + (1/2)n
i=1
-- same as n(n+1)/2 derived in earlier posts. How about
if I'm summing numbers to the 2nd power, what are my
coefficients?
>>> bernoulli.coeffs(2)
[(1, 3), (1, 2), (2L, 12L)]
i.e.
n
SIGMA n^2 = (1/2)n^3 + (1/2)n^2 + (1/6)^n
i=1
So, to answer one of our earlier questions, what's
1^7 + 2^7 + 3^7 +... + (n-1)^7 + n^7
expressed as an 8th degree polynomial in terms of n?
= (1/8)n^8 + (1/2)n^7 + (7/12)n^6 - (210/720)n^4 + (2520/30240)n^2
I have a function, poly() that will actually apply the
coefficients to powers of n and compute this sum. Let's
compute a few values:
>>> bernoulli.poly(10,7) # 1^7 + ... + 10^7
18080424.9999999999999999999999+-2
>>> bernoulli.poly(11,7) # 1^7 + ... + 11^7
37567595.9999999999999999999999+-2
>>> bernoulli.poly(12,7) # 1^7 + ... + 12^7
73399404.0000000000000000000000+-2
The slightly off results come from working with decimals of
limited precision. Now let's compute these sums more directly,
by defining f(x) = x^7 and passing f as a parameter to our
usual:
n
g(f,n) = SIGMA f(i)
i=1
>>> bernoulli.g(f,10)
18080425
>>> bernoulli.g(f,11)
37567596
>>> bernoulli.g(f,12)
73399404
Same answers, approximately. If we're persuade the
algorithm is correct, we could convert to integers as a
last step in poly(), thereby assuring whole number answers.
Kirby
[1] module by Jurjen N.E. Bos:
ftp://ftp.python.org/pub/python/contrib-09-Dec-1999/
DataStructures/real-accurate.pyar
[2] bernoulli.py by K. Urner
http://www.inetarena.com/~pdx4d/ocn/python/bernoulli.py