Factorials in difference
triangles
By Michael Swarbrick-Jones (P1515) on
Sunday, April 2, 2000 - 11:52 am :
I've recently come across a problem that nobody at my school
or a 6th-form can figure out. I came across it while learning
about the difference method for figuring out what the formula for
a series in the form of a polynomial is.
If you look at the difference table of the square numbers:
| 1 |
|
4 |
|
9 |
|
16 |
|
25 |
|
|
3 |
|
5 |
|
7 |
|
19 |
|
|
|
2 |
|
2 |
|
2 |
|
-the constant is 2
If you look at the triangle for cube numbers:
| 1 |
|
8 |
|
27 |
|
64 |
|
125 |
|
|
7 |
|
19 |
|
37 |
|
61 |
|
|
|
12 |
|
18 |
|
24 |
|
|
|
|
6 |
|
6 |
|
|
|
- the constant is 6
the constant for quadric numbers is 24
the constant for quintic numbers is 120
the constant for hexic(?) numbers is 720
my theory is that the constant for degree n is n!
( n factorial ) and it works up to degree 10 but no-one has been
able to convince me of this.
I think you have to use induction and two people claim to have
seen a proof. I have proved by induction that this puzzle is
equivalent to:
|
æ
ç
è
|
|
ö
÷
ø
|
na - |
æ
ç
è
|
|
ö
÷
ø
|
(n-1)a+ |
æ
ç
è
|
|
ö
÷
ø
|
(n-2)a+¼+(-1)r |
æ
ç
è
|
|
ö
÷
ø
|
(n-r)a+¼ = a!
|
I know there is a proof (because someone has seen one)
but can any one help?
By Michael Doré (P904) on Monday, April 3,
2000 - 09:49 pm :
This looks a bit suspect. If you set n = 2 you get:
2a - 2 = a!
What I think you mean is:
|
|
n
å
r=0
|
(r+1)n |
æ
ç
è
|
|
ö
÷
ø
|
(-1)r+n=n! |
|
This is certainly an equivalent statement to the theory
you're trying to prove. And it appears to work, but I can't yet
prove this directly. Here I used (n r) = n choose r.
However, I think I can prove the theory using a different method,
but I'm not at all sure, so it would be worth checking the
following argument.
Suppose we are dealing with the nth power. The first line should
read:
1n 2n 3n ... (x-1)n
xn (x+1)n ...
Now suppose you apply the difference method once, let's say
between (x-1)n and xn . We get a polynomial
of degree n-1. If you go to the next difference term (across the
page - i.e. the difference between (x+1)n and
xn ) you get the same polynomial with x replaced by
x+1. (Do you agree?)
Now after applying the difference method r times, the order of
the polynomial in x (at any point) is n-r (or lower). This can be
proven by induction.
Suppose after applying the difference method k times we have a
polynomial of n-k, at each point. Now the polynomial either side
of it (on the same line) will simply have the x replaced with x-1
or x+1. Therefore when you binomially expand each term the
coefficient of xn-k is the same. Therefore the
xn-k s will cancel and the differences will have an
order of no higher than n-k-1. After applying the difference
method 0 times you get a polynomial of degree n-k = n-0 = n, so
this completes the induction proof that the degree of the
polynomial after r differences will be n-r.
Now let's keep an eye on the leading co-efficient of the
polynomial at each point. Suppose at some point after applying
the difference procedure r times the leading coefficient was A,
making the polynomial:
Axn-r + Bxn-r-1 + Cxn-r-2 + ...
+ @x+#
where B C ... @ # are more constants.
Now if you look at the term one to the right of this you
have:
A(x+1)n-r + B(x+1)n-r-1 +
C(x+1)n-r-2 + ... +@(x+1) + #
Now we subtract these.
The coefficient of xn-r --- zero (as we've already
said)
The coefficient of xn-r-1 --- A(n-r) - check this
using the binomial expansion.
And this coefficient is the same everywhere. So each time you
apply the difference procedure, the degree of the polynomial goes
down by one, and its leading co-efficient is multiplied by
(n-r).
So to get from a polynomial of degree n, to degree zero (the
constant we're after) we apply the difference method n times and
the leading co-effient (i.e. the hanging constant, what we're
trying to find) is n(n-1)(n-2)(n-3)...3 2 1 = n! as
required.
This also indirectly proves that:
|
|
n
å
r=0
|
(r+1)n |
æ
ç
è
|
|
ö
÷
ø
|
(-1)r+n=n! |
|
but does anyone know how to prove this more directly?
Hope that's all right,
Michael
By Michael Doré (P904) on Tuesday, April 4,
2000 - 09:26 am :
Sorry, I think I have been misusing a term. Where I wrote "the
order of the polynomial" this should be read as the degree of the
polynomial, or the highest power in it. The order/degree of the
polynomial 1/3x3 + 10x2 + 7x + 3.5 is 3,
because of the x3 term.
Sorry about that,
Michael