2

We had a high school mathematics teacher who taught us a cool technique that I've forgotten. It can be used, for example, for developing a formula for the sum of squares for the first "n" integers. You start by making a column for Sn, and then determine the differences until you get a constant. See the picture.

example - sorry about the rotated picture (sorry about the rotated picture)

How do you proceed from here to the formula?

Joffan
  • 39,627
Eric Duncan
  • 21
  • 1
    A helpful discussion here of the finite difference approach: http://math.stackexchange.com/a/316753/215011 – grand_chat Jun 03 '16 at 20:53

2 Answers2

4

Every polynomial that takes integer values over the integers can be represented with respect to the binomial base as a linear combination with integer coefficients. In our case:

$$ n^2 = \color{blue}{2}\binom{n}{2}+\color{blue}{1}\binom{n}{1}+\color{blue}{0}\binom{n}{0} \tag{1}$$ And that leads to: $$ \sum_{n=1}^{N}n^2 = 2\binom{N+1}{3}+1\binom{N+1}{2}+0\binom{N+1}{1} = \frac{N(N+1)(2N+1)}{6}.\tag{2} $$ The blue coefficients appearing in $(1)$ can be computed through the forward difference operator: $$ \begin{array}{ccccccccc} \color{blue}{0} && 1 && 4 && 9 && 16 \\ &\color{blue}{1} && 3 && 5 && 7 && \\ && \color{blue}{2} && 2 && 2 &&& \end{array}\tag{3}$$

Another example, for $n^3$. $$ \begin{array}{ccccccccc} \color{blue}{0} && 1 && 8 && 27 && 64 \\ &\color{blue}{1} && 7 && 19 && 37 && \\ && \color{blue}{6} && 12 && 18 &&& \\ &&& \color{blue}{6} && 6 \end{array}\tag{3bis}$$ Gives: $$ n^3 = \color{blue}{6}\binom{n}{3}+\color{blue}{6}\binom{n}{2}+\color{blue}{1}\binom{n}{1}\tag{1bis} $$ hence: $$ \sum_{n=1}^{N}n^3 = 6\binom{N+1}{4}+6\binom{N+1}{3}+1\binom{N+1}{2}=\left(\frac{N(N+1)}{2}\right)^2.\tag{2bis}$$

You may be also interested in knowing that our "magic blue numbers" just depend on Stirling numbers of the second kind.

Jack D'Aurizio
  • 353,855
  • What/where is the background for step (1)? Thanks. – Eric Duncan Jun 03 '16 at 21:11
  • @EricDuncan: $(1)$ is a consequence of $(3)$. Read it this way: $(3)\mapsto (1)\mapsto (2)$ and $(3bis)\mapsto (1bis)\mapsto (2bis)$. – Jack D'Aurizio Jun 03 '16 at 21:13
  • I'm afraid that without a worked example of the forward difference operator , I'm clueless as to where the blue coefficients come from. I'll do some background reading before I post again. – Eric Duncan Jun 03 '16 at 21:26
  • @EricDuncan: there are two worked examples here. In $(3)$ and $(3bis)$, every coefficient is the difference between the coefficient at its top right and the coefficient at its top left. The blue coefficients are the first coefficients of every line. – Jack D'Aurizio Jun 03 '16 at 21:32
0
  • backgrounded on the fact that the difference of two consecutive squares is an odd number:

$(n+1)^2-n^2=2n+1$

the difference of two consecutive odd numbers is always $2$ thus the self-saying technique.

So when we proceed to find a square $n^2$ we sum up all odd numbers from 1 to $2n-1$ which is an arithmetic sequence of distance 2.

$n^2=\frac{n(2n)}{2}=\frac{\frac{(2n)(2n)}{2}}{2}=\frac{\frac{(2n-1)(2n)}{2}+n}{2}=\frac{\binom{2n}{2}+n}{2}$

Also we note that

$n^2=\frac{\frac{(2n)(2n)}{2}}{2}=\frac{\frac{(2n+1)(2n)}{2}-n}{2}=\frac{\binom{2n+1}{2}-n}{2}$

Summing up the two sums of two formulas $$\sum_n{\frac{\binom{2i}{2}+n}{2}}+\sum_n{\frac{\binom{2i+1}{2}-n}{2}}=\sum_n{\frac{\binom{2i}{2}+\binom{2i+1}{2}}{2}}=\sum_{2n+1}{\frac{\binom{i}{2}}{2}}=2\sum{i^2}$$ is just the sum of values in second column of pascal triangle (even and odd binomials) until $2n+1$, divided by 2.

    1
    1 1 
    1 2  |1 |
    1 3  |3 | 1
    1 4  |6 | 4  1
    1 5  |10| 10 5  1
    1 6  |15| 20 15 6 1
    . .   \  \
    . .    \  \
    . .     \  \
    1 7   21 \35\ .  .  .  .

Summing up the second column will result in the next row/column situated pascal value, which is known to be $\binom{2n+2}{3}$

So ... $$2\sum_n{i^2}=\frac{\binom{2n+2}{3}}{2}=\frac{\frac{2n(2n+1)(2n+2)}{6}}{2}$$

Abr001am
  • 746