Monthly Archives: July 2017

Little Bird and a Recursive Generator

Screen Shot 2017-07-01 at 3.26.21 PM.png

When I was asked to prove the following power summation formulas by mathematical induction:

\sum\limits_{i=1}^{n}i = 1+2+3+...+n=\frac{n (n+1)}{2},

\sum\limits_{i=1}^{n}i^2=1^2+2^2+3^2+...+n^2= \frac{n (n+1) (2n +1)}{6},

\sum\limits_{i=1}^{n}i^3=1^3+2^3+...+n^3 = \frac{n^2 (n+1)^2}{4},

I wondered how these closed forms are obtained in the first place!  Did a little bird whisper the formulas into our ears?

Even though there are elementary derivations of the power summation formulas, for example,  the visual derivations in Proof Without Words by MAA, none goes beyond the 3rd power.

In this blog, I will construct a recursive generator capable of generating the closed form of power summation

\sum\limits_{i=1}^{n}i^p,

for all p \in N^{+}.

Let us start with a picture.

screen-shot-2017-07-02-at-3-49-48-pm.png

Fig. 1

Let A denotes the area of a rectangle, Fig.1 shows

\sum A_{blue} = A_{n^p \times n} - \sum A_{yellow}.

Since

\sum A_{blue} = \sum\limits_{i=1}^{n}i^p,

A_{n^p\times n} = n^p n,

\sum A_{yellow}= \sum\limits_{i=1}^{n-1}i((i+1)^p-i^p),

we have

\sum\limits_{i=1}^{n}i^p = n^p n - \sum\limits_{i=1}^{n-1}i((i+1)^p-i^p)\quad\quad\quad(1).

when p = 1, (1) becomes

\sum \limits_{i=1}^{n}i=n^2-\sum\limits_{i=1}^{n-1}i((i+1)-i)

= n^2-(\sum\limits_{i=1}^{n}(i(i+1)-i)-(n(n+1)-n))

= n^2-\sum\limits_{i=1}^{n}i+n,

hence,

2\sum\limits_{i=1}^{n}i=n^2+n,

or,

\sum\limits_{i=1}^{n}i=\frac{n(n+1)}{2}\quad\quad\quad(2).

When p = 2,

\sum\limits_{i=1}^{n}i^2=n^2 n-\sum\limits_{i=1}^{n-1}i((i+1)^2-i^2)

= n^3-2\sum \limits_{i=1}^{n}i^2-\sum\limits_{i=1}^{n}i+2n^2+n.

Substituting (2) for \sum\limits_{i=1}^{n}i,  we have

3\sum\limits_{i=1}^{n}i^2=n^3-\frac{n(n+1)}{2}+2n^2+n

or,

\sum\limits_{i=1}^{n}i^2= \frac{n(n+1)(2n+1)}{6}.

In general, \forall p \in N^+,

\sum\limits_{i=1}^{n}i^p = n^p n-\sum\limits_{i=1}^{n-1}i((i+1)^p-i^p)

= n^{p+1}-(\sum\limits_{i=1}^{n}i((i+1)^p-i^p)-n((n+1)^p-n^p))

= n^{p+1}-     \sum\limits_{i=1}^{n}(i(\sum\limits_{j=0}^{p}\binom{p}{j}i^{p-j}-i^p))        +n((n+1)^p-n^p)

=n(n+1)^p-\sum\limits_{i=1}^{n}(i\sum\limits_{j=1}^{p}\binom{p}{j}i^{p-j})

= n(n+1)^p - \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{p}\binom{p}{j}i^{p-j+1}

= n(n+1)^p - \sum\limits_{i=1}^{n}(p i^p + \sum\limits_{j=2}^{p}\binom{p}{j}i^{p-j+1})

= n(n+1)^p - p\sum\limits_{i=1}^{n}i^p-\sum\limits_{i=1}^{n}\sum\limits_{j=2}^{p}\binom{p}{j}i^{p-j+1}

= n(n+1)^p-p\sum\limits_{i=1}^{n}i^p-\sum\limits_{j=2}^{p}\sum\limits_{i=1}^{n}\binom{p}{j}i^{p-j+1}

= n(n+1)^p-p\sum\limits_{i=1}^{n}i^p-\sum\limits_{j=2}^{p}(\binom{p}{j}\sum\limits_{i=1}^{n}i^{p-j+1}).

Solving for \sum\limits_{i=1}^{n}i^p, we obtain

\sum\limits_{i=1}^{n}i^p = \frac{n(n+1)^p -\sum\limits_{j=2}^{p}(\binom{p}{j}\sum\limits_{i=1}^{n}i^{p-j+1}) }{p+1}.

Let

s_p \triangleq \sum\limits_{i=1}^{n}i^p,

then

s_p = \frac{n(n+1)^p - \sum\limits_{j=2}^{p}\binom{p}{j} s_{p-j+1}}{p+1}\quad\quad\quad(3)

What we have here is a recursive generator capable of  generating  power summation formulas for virtually all integrer powers. Implemented in Omega CAS Explorer,  the figures below illustrate the awesomeness of this generator:

Screen Shot 2017-07-04 at 6.20.59 PM

Fig. 2

Screen Shot 2017-07-04 at 6.23.26 PM.png

Fig. 3

Advertisements

Chaplin or Leibniz ?

Charlie_Chaplin_Factory_Work

Before I do proofs via the 3-step mathematical induction, the classic Charlie Chaplin movie clip often comes to my mind. It nudges me to seek better ways. For example, to prove

(k+1)(1^k+2^k+3^k+\dots+n^k)<(n+1)^{k+1}, \quad k, n \in N^+,

Instead of applying the 3-step mathematical induction, let us look at Fig. 1.

Screen Shot 2017-07-07 at 6.44.28 PM.png

Fig. 1

If A denotes the total area of the blue rectangles, Fig.1 shows

A=1\cdot 1^k+1\cdot 2^k+1\cdot 3^k+\dots+1\cdot n^k = 1^k+2^k+3^k+\dots+n^k.

It also shows that

A < the  area under the curve x^k = \int\limits_{0}^{n+1}x^k\; dx.

By the fundamental theorem of calculus,

\int\limits_{0}^{n+1}x^k\;dx = \frac{x^{k+1}}{k+1}\bigg|_{0}^{n+1}=\frac{(n+1)^{k+1}}{k+1}.

Therefore,

1^k+2^k+3^k+\dots+n^k < \frac{(n+1)^{k+1}}{k+1},

i.e.,

(k+1)(1^k+2^k+3^k+\dots+n^k)<(n+1)^{k+1}, \quad\quad k, n \in N^+.

This proof suggests another inequality:

(k+1)(1^k+2^k+3^k+\dots+n^k)>n^{k+1}, \quad\quad k, n \in N^+.