4
$\begingroup$

Is this a thing? If not, can anyone help me out on this?

So I saw this a while back.$$\sum_{i=0}^n(2n + 1) = n^2$$ For positve n. This is interesting, and I wondered if I could write any n^x in sigma notation.

Here was my thought process. Take the difference of the powers, to find a pattern. This for $n^2$ gives:

0 1 4 9 16 25...

1 3 5 7 9...

2 2 2 2...

So this says that the difference of consecutive squares are odd numbers that increase by two. $2^7$ could be said as $1+3+5+7+9+11+13$.

For cubes I did the same.

0 1 8 27 64 125...

1 7 19 37 61...

6 12 18 24...

6 6 6...

This says that that the difference of the differences of the differences(pls no more redundancy) of a set of cubes is 6. $6^3$ can be said as $1+7+19+37+61+91$.

This in sigma notation is $$\sum_{i=0}^n(2n + 1) = n^2$$ and$$\sum_{i=0}^n((\sum_{j=0}^{i}6j) + 1) = n^3$$

I programmed a tool to help me find the num that the differences boil down to.

We know that 2's is 2, 3's is 6.

I calculated it for 3 more then found something.

4: 24

5: 120

6: 720

These were all factorials. $5! = 120, 6! =720$ and so on.

These equations will all contain these numbers.

I think that n to the xth power would have x sigmas that sum each other, with the last sigma summing x!. This is most likely close but wrong.

I'm missing a lot of info on this, I need to think more.

$\endgroup$
  • 1
    $\begingroup$ It seems to me that $\sum_{i=0}^n(2n + 1) = (n+1)^2$ and that $\sum_{i=0}^n((\sum_{j=0}^{i}6j) + 1) = (n+1)^3$ $\endgroup$ – Claude Leibovici Feb 21 '15 at 4:30
  • $\begingroup$ @ClaudeLeibovici Also it's actually $\sum_{i=0}^n(2i + 1) = (n+1)^2$ $\endgroup$ – user26486 Feb 21 '15 at 4:45
  • $\begingroup$ @user314. Thanks for pointing the typo ! $\endgroup$ – Claude Leibovici Feb 21 '15 at 4:46
  • 2
    $\begingroup$ The magic phrase that you might want to look for is 'finite differences' - taking finite difference of a sequence is very analogous to differentiating a function (if you're familiar with calculus) and in particular the fact that the $d$'th finite difference of the sequence $\{n^d\}$ is the constant sequence $d!$ is well-known. It's also very accessible; if you're interested I can write you up a short proof. $\endgroup$ – Steven Stadnicki Feb 21 '15 at 4:49
  • $\begingroup$ Just as $f(x) = f(0) + \int_0^x f'(s) ds $, $ f_N = f_0 + \sum_{i=0}^{N-1} (Df)_i $, where $D$ is a discrete difference operator: $(Df)_i = f_{i+1}-f_i$. $\endgroup$ – littleO Feb 21 '15 at 8:28
1
$\begingroup$

The summation formulas get cumbersome after more than one or two $\sum$ symbols occur, so I'll invent a little special-purpose notation. (Or reinvent a notation, as I think someone else has probably used notation with a similar purpose before.)

Let $$\newcommand{\msum}[2]{#1^{\langle{#2}\rangle}} \begin{eqnarray} \msum N0 &=& 1,\\ \msum Np &=& p \sum_{n=1}^N \msum np \quad \mbox{for}\quad p > 0. \end{eqnarray}$$

Then $$\begin{eqnarray} \msum{N}{1} &=& 1 \sum_{n=1}^N 1 = N,\\ \msum{N}{2} &=& 2 \sum_{n=1}^N \sum_{m=1}^n 1 = (N+1)N,\\ \msum{N}{3} &=& 6 \sum_{n=1}^N \sum_{m=1}^n \sum_{k=1}^m 1 = (N+2)(N+1)N, \end{eqnarray}$$ and so forth. In general,

$$\msum{N}{p} = (N + p - 1)(N + p - 2)\cdots(N + 2)(N + 1)N.$$

Clearly $$N^2 = (N+1)N - N = \msum{N}{2} - \msum{N}{1}.$$

In order to write higher powers of $N$ in terms of these sums, it will be useful to derive such equations for various values of $m$ and $k$ in $(N+m)(N+m-1)\cdots(N+2)(N+1)N^k$ and to reuse those equations while working on higher powers. For example, $$\begin{eqnarray} (N+1)N^2 &=& (N+2)(N+1)N - 2(N+1)N \\ &=& \msum N3 - 2\msum N2,\\ N^3 &=& (N+1)N^2 - N^2 = \msum N3 - 2\msum N2 - (\msum N2 - \msum N1) \\ &=& \msum N3 - 3\msum N2 + \msum N1, \\ &&\\ (N+2)(N+1)N^2 &=& (N+3)(N+2)(N+1)N - 3(N+2)(N+1)N \\ &=& \msum N4 - 3\msum N3,\\ (N+1)N^3 &=& (N+2)(N+1)N^2 - 2(N+1)N^2 \\ &=& \msum N4 - 3\msum N3 - 2(\msum N3 - 2\msum N2),\\ &=& \msum N4 - 5\msum N3 + 4\msum N2,\\ N^4 &=& (N+1)N^3 - N^3 \\ &=& \msum N4 - 5\msum N3 + 4\msum N2 - (\msum N3 - 3\msum N2 + \msum N1) \\ &=& \msum N4 - 6\msum N3 + 7\msum N2 - \msum N1, \\ &&\\ (N+3)(N+2)(N+1)N^2 &=& (N+4)(N+3)(N+2)(N+1)N \\ && \qquad - 4(N+3)(N+2)(N+1)N \\ &=& \msum N5 - 4\msum N4,\\ (N+2)(N+1)N^3 &=& (N+3)(N+2)(N+1)N^2 - 3(N+2)(N+1)N^2 \\ &=& \msum N5 - 4\msum N4 - 3(\msum N4 - 3\msum N3) \\ &=& \msum N5 - 7\msum N4 + 9\msum N3,\\ (N+1)N^4 &=& (N+2)(N+1)N^3 - 2(N+1)N^3 \\ &=& \msum N5 - 7\msum N4 + 9\msum N3 - 2(\msum N4 - 5\msum N3 + 4\msum N2),\\ &=& \msum N5 - 9\msum N4 + 19\msum N3 - 8\msum N2,\\ N^5 &=& (N+1)N^4 - N^4 \\ &=& \msum N5 - 9\msum N4 + 19\msum N3 - 8\msum N2 \\ && \qquad - (\msum N4 - 6\msum N3 + 7\msum N2 - \msum N1) \\ &=& \msum N5 - 10\msum N4 + 25\msum N3 -15\msum N2 + \msum N1, \\ \end{eqnarray}$$ so it's tedious but not difficult to continue on toward any positive integer power of $N$, and you could easily program a computer to write the formula for $N^p$ in this fashion.

But we also have $$\begin{eqnarray} \msum{N}{1} &=& 1 \sum_{n=1}^N 1 = N,\\ \msum{N}{2} &=& 2 \sum_{n=1}^N \sum_{m=1}^n 1,\\ \msum{N}{3} &=& 6 \sum_{n=1}^N \sum_{m=1}^n \sum_{k=1}^m 1, \end{eqnarray}$$ and so forth. Since each index of summation appears only as the number of terms of the next inner sum, if we assume that the index of each sum always runs from $1$ to the index of the next outermost sum, except for the outermost sum (which runs from $1$ to $N$), then we can also write $$\begin{eqnarray} \msum{N}{2} &=& 2 \sum \sum 1 = \sum \sum 2!,\\ \msum{N}{3} &=& 6 \sum \sum \sum 1 = \sum \sum \sum 3!, \end{eqnarray}$$ and in general, $$\msum{N}{p} = \underbrace{\sum \sum \cdots \sum}_{\text{$n$ times}} p!.$$

Observing that $$\sum\left(\underbrace{\sum \sum \cdots \sum}_{\text{$n$ times}} b + a\right) = \underbrace{\sum \sum \cdots \sum}_{\text{$n+1$ times}} b + \underbrace{\sum \sum \cdots \sum}_{\text{$n$ times}} a,$$

we can write $$\begin{align} a_p\msum {N&}p + a_{p-1}\msum Np + \cdots + a_2\msum N3 + a_2\msum N2 + a_1\msum N1 \\ &= \sum\left( \sum\left( \sum\left( \cdots \sum\left( \sum p!a_p + (p-1)!a_{p-1}\right) \cdots + 3!a_3\right) + 2!a_2\right) + a_1\right) \end{align}$$

We can then rewrite the equations already found for $N^p$ as follows:

$$\begin{eqnarray} N &=& \sum 1, \\ N^2 &=& \sum\left( \sum 2 - 1 \right), \\ N^3 &=& \sum\left( \sum\left( \sum 6 - 6 \right) + 1\right), \\ N^4 &=& \sum\left( \sum\left( \sum\left( \sum 24 - 36 \right) + 14\right) - 1\right),\\ N^5 &=& \sum\left( \sum\left( \sum\left( \sum\left( \sum 120 - 240 \right) + 150\right) - 30\right) + 1\right). \end{eqnarray}$$

Indeed the first term in this expansion of $N^p$ is always $p!$, as you thought, the last is always $\pm 1,$ and the other terms are multiples of $q!$ for $q = p-1, p-2, \ldots, 2.$

$\endgroup$
2
$\begingroup$

Here are a few ideas:


$$(n+1)^2-n^2~=~2n+1,\qquad\qquad(n+1)^3-n^3~=~3n^2+3n+1,\qquad\text{etc.}$$


$$\sum_{n=0}^Nn~=~\frac{N(N+1)}{2!}~,\qquad\qquad\sum_{k=0}^N~\sum_{n=0}^kn~=~\frac{N(N+1)(N+2)}{3!}$$

$$~$$

$$\sum_{k=0}^N~\sum_{m=0}^k~\sum_{n=0}^mn~=~\frac{N(N+1)(N+2)(N+3)}{4!}~,\qquad\quad\text{etc.}$$


$$\sum_{n=0}^Nn~=~\frac{N(N+1)}2~,\qquad\qquad\sum_{n=0}^Nn(n+1)~=~\frac{N(N+1)(N+2)}3$$

$$~$$

$$\sum_{n=0}^Nn(n+1)(n+2)~=~\frac{N(N+1)(N+2)(N+3)}4~,\qquad\quad\text{etc.}$$

$\endgroup$
  • $\begingroup$ It's $\sum_{k=0}^N~\sum_{n=0}^kn~=~\sum_{n=0}^N\frac{n(n+1)}{2}~=~\frac{N(N+1)(N+2)}6$ $\endgroup$ – user26486 Feb 21 '15 at 4:19
  • $\begingroup$ Also $\sum_{k=0}^N~\sum_{m=0}^k~ \sum_{n=0}^mn~=~ \sum_{n=0}^N\frac{n(n+1)(n+2)}{6}~=~ \frac{N(N+1)(N+2)(N+3)}{24}~$ $\endgroup$ – user26486 Feb 21 '15 at 4:24
  • $\begingroup$ $$\underbrace{(n+1)(n+2)⋯(n+k+1)}_{u_{n+1}}−\underbrace {n(n+1)⋯(n+‌​k)}_{u_n}=(k+1)(n+1)(n+2)(n+3)⋯(n+k)$$ You can telescope....... and use induction. $\endgroup$ – Bumblebee Feb 21 '15 at 6:13
  • $\begingroup$ @user314: Thank you. I've corrected it. :-$)$ $\endgroup$ – Lucian Feb 21 '15 at 12:15
1
$\begingroup$

perhaps the most interesting single fact to emerge from your investigation is the relation: $$ \sum_{k=1}^n (-1)^{n-k}\binom{n}{k}k^n = n! $$ this may be derived by applying the inclusion-exclusion principle to counting the endomorphisms of a set containing $n$ elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.