The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: 1 + 2 + ... + n a polynomial how?
Replies: 5   Last Post: Apr 2, 2013 11:55 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
David C. Ullrich

Posts: 3,555
Registered: 12/13/04
Re: 1 + 2 + ... + n a polynomial how?
Posted: Apr 2, 2013 11:55 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 01 Apr 2013 19:18:54 +0300, Jussi Piitulainen
<> wrote:

>Is it obvious that 1 + 2 + ... + n is a polynomial of degree 2? How?
>I mean the sum of the first n positive integers. I would like to see
>that it is a polynomial of degree 2 _without using_ the fact that it
>is equal to n(n + 1)/2. Zeilberger (his new Opinion 129) says Gauss
>could have used the polynomiality of the sum to support the equality,
>rather than the other way around.

We'll write sequences using parentheses instead of subscripts,
because we need subscripts to index sequences of sequences:
If s is a sequence then s is the sequence

s = (s(0), s(1), ...) .

We'll say a sequence "is" a polynomial if there exists a
polynomial p with s(n) = p(n).

Given a sequence s, we define the sequence Ds by

(Ds)(n) = s(n+1) - s(n).

Various people have replied that the reason your sequence
s is a polynomial is that Ds is a polynomial. You _knew_ that
Ds is a polynomial, so just saying that it follows that s is
a polynomial is presumably no help, you want to know
_why_ it follows that s is a polynomial.

Thought about it for a minute, came up with a proof
with a reasonably high concept/calculation ratio.

Say P_N is the space of all polynomials of degree
less than or equal to N. The result follows from this:

Prop. If s is in P_N then there exists q in P_{N+1}
with Dq = s.

That's not exactly what you need, but you know
how to fill the tiny gap.

Lemma. If p_j is a polynomial of degrree exactly j
then p_0, ... , p_N are linearly independent.

The grubbing around with coefficients and systems
of equations if contained in the proof of the lemma.
But luckily there's no need to write that proof down,
because I'm sure you agree the lemma is obvious.

Let b_j denote the monomial sequence

b_j(n) = n^j.

So in particular b_0, ... b_N is a basis for P_N.

It's clear that q in P_{N+1} implies Dq is in P_N.

So we fix N and regard D as an operator from
P_{N+1} to P_N.

Now it's clear that the degree of Db_j is exactly
j - 1, at least for j >= 1. Hence the lemma shows that
Db_1, ... , Db_{N+1} are independent.

So D(P_{N+1}) is a subspace of P_N, and
the dimension of D(P_{N+1}) is at least N+1.
Hence D(P_{N+1}) = P_N. QED.

>Thanks for any insight.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.