# Combinatorial Proofs for Summations: A Possible Generalisation?

\begin{equation*} \sum_{r=1}^{n} r^\alpha (n-r)^\beta = ? \end{equation*} where $\alpha$ and $\beta$ are natural numbers

Background:

Here's something I wish to share with the Math SE community, a very interesting combinatorial proof, that I came across sometime ago. I strongly believe,that this approach could lead to a possible generalisation of similar summations.

Those who wish to read the following warm-up proofs (I thought it's a good idea to share what motivated me towards asking the problem I intend to ask), may do so while enjoying the little snack for the mind - the art of combinatorial proof. Others, may skip directly to the question I intend to ask, right after these proofs.

\begin{equation*} 1 + 2 + 3 + \cdots + n = {n+1 \choose 2} \end{equation*}

The above identity is a very familiar one, apparently one that Gauss came up with when his teacher asked him to sum up numbers from 1 to 100 (supposed to be punishment). Of course, his proof is well known - writing the sequence in the reverse order and summing it with the original one greatly reduces computational effort.

Now, what's interesting is the combinatorial approach, which I summarise as follows (for people who may not be familiar with it)-

In general, to give a combinatorial proof for a binomial identity, say A=B you do the following:

Find a counting problem you will be able to answer in two ways. Explain why one answer to the counting problem is A. Explain why the other answer to the counting problem is B. Since both A and B are the answers to the same question, we must have A=B.

The tricky thing is coming up with the question. This is not always obvious, but it gets easier the more counting problems you solve. You will start to recognize types of answers as the answers to types of questions. More often what will happen is you will be solving a counting problem and happen to think up two different ways of finding the answer. Now you have a binomial identity and the proof is right there. The proof is the problem you just solved together with your two solutions.

Now, coming to the proof of the above-stated identity-

Consider the question:"How many subsets of $A = {1,2,3, \ldots, n+1}$ contain exactly two elements?" Answer 1: We must choose 2 elements from $n+1$ in set A, so there are exactly ${n+1 \choose 2}$ subsets.

Answer 2: We break this question down into cases, based on what the larger of the two elements in the subset is. The larger element can't be 1, since we need at least one element smaller than it.

Larger element is 2: there is 1 choice for the smaller element.

Larger element is 3: there are 2 choices for the smaller element.

Larger element is 4: there are 3 choices for the smaller element. And so on. When the larger element is $n+1$, there are $n$ choices for the smaller element. Since each two element subset must be in exactly one of these cases, the total number of two element subsets is $1 + 2 + 3 + \cdots + n\text{.}$

Answer 1 and answer 2 are both correct answers to the same question, so they must be equal. Therefore, \begin{equation*} 1 + 2 + 3 + \cdots + n = {n+1 \choose 2} \end{equation*}

To drive y'all another step closer to my question, here's another (just one) combinatorial proof: \begin{equation*} 1(n) + 2(n-1) + 3 (n-2) + \cdots + (n-1) 2 + n(1) = {n+2 \choose 3}. \end{equation*}

Consider the question “How many 3-element subsets are there of the set $\{1,2,3,\ldots, n+2\}\text{?}$"

Answer 1: We must select 3 elements from the collection of $n+2$ elements. This can be done in ${n+2 \choose 3}$ ways.

Answer 2: Break this problem up into cases by what the middle number in the subset is. Say each subset is $\{a,b,c\}$ written in increasing order. We count the number of subsets for each distinct value of $b$. The smallest possible value of $b$ is $2$ and the largest is $n+1$

When $b=2$, there are $1(n)$ subsets: 1 choice for $a$ and $n$ choices (3 through $n+2$) for $c$

When $b=3$, there are $2(n-1)$ subsets: 2 choices for $a$ and $n-1$ choices for $c$

When $b=4$, there are $3(n-2)$ subsets: 3 choices for $a$ and $n-2$ choices (3 through $n+2$) for $c$

And so on. When $b=n+1$ there are $n$ choices for $a$ and only 1 choice for $c$, so, $n(1)$ subsets.

Therefore, the total number of subsets is $1(n) + 2(n-1) + 3 (n-2) + \cdots + (n-1) 2 + n(1)$.

Therefore, \begin{equation*} 1(n) + 2(n-1) + 3 (n-2) + \cdots + (n-1) 2 + n(1) = {n+2 \choose 3}. \end{equation*}

This, sort of hints at a pattern, in summations involving r and n-r multiplied, raised to different powers(r varying from 1 to n). Finally, my question is: \begin{equation*} \sum_{r=1}^{n} r^\alpha (n-r)^\beta = ? \end{equation*} where $\alpha$ and $\beta$ are natural numbers

I need help not only in solving for the answer to the above summation in terms of $\alpha$ and $\beta$, but also figuring out a combinatorial approach. The power of the art of combinatorial proof convinces me that the above summation, a generalisation of what we have seen till now - can be possibly evaluated using combinatorial techniques/arguments.

Edit: Something just struck me. Can we look at possible recursion, for the given sum? We know how to solve the easy cases, like ($\alpha$,$\beta$)= (0,1) or (1,0). Is it possible to find a recursion of S($\alpha$,$\beta$) in terms of S($\alpha$-1,$\beta$), or S($\alpha$,$\beta$-2), etc, where S denotes the required sum with parameters ($\alpha$,$\beta$)

• Combinatorial proof means that formal power series technics are out of question, doesn't it? – Clément Guérin Mar 1 '18 at 9:14
• Also, as a sidenote, taking $\beta=0$ leaves you with the sum of $\alpha$-powers of the first $n$ integers. There are some formulation of this in terms of Stierling numbers of the second kind and binomial coefficients. The proof is not combinatorial (it uses some formula involving Stierling numbers). Stierling numbers count the number of partitions such that... and binomial coefficients count the number of subsets such that... Well my point is that both have a combinatorial interpretations. Maybe you can figure out something in the case $\beta=0$ with said formula. – Clément Guérin Mar 1 '18 at 9:25
• @ClémentGuérin, you may solve it using non-combinatorial techniques as well, for starters. Once we figure out the closed form of that summation, maybe we can brainstorm towards a combinatorial approach. – arya_stark Mar 1 '18 at 9:48
• @schrodinger_16 There is an algorithm for finding out if the given formula has a closed form with a (certain) bounded polynomial degree. Check out A=B from Petkovsek, Wilf and Zeilberger, online here: math.upenn.edu/~wilf/AeqB.html – SK19 Mar 3 '18 at 11:23
• @SK19, there is no doubt that this summation has a closed form. If given particular values of $\alpha$ and $\beta$, one may use binomial expansion to express that sum as a polynomial in r. Once this is done, we know that summation of r^k for values of k = 1,2,3,4... and so on can be evaluated. – arya_stark Mar 3 '18 at 11:28

The subject is indeed interesting, but here we can just introduce the main lines along which it could be analized.

Let's change symbols and consider the function $$\bbox[lightyellow] { S(a,b,n) = S(b,a,n) = \sum\limits_{0\, \le \,k\, \le \,n} {k^{\,a} \left( {n - k} \right)^{\,b} } = \sum\limits_{1\, \le \,k\, \le \,n - 1} {k^{\,a} \left( {n - k} \right)^{\,b} } \quad \left| \matrix{ \;0 \le n \in \mathbb Z \hfill \cr \;0 < a,b \in \mathbb R \hfill \cr} \right. }$$ where for generality we admit that $a$ and $b$ be positive reals. We will deal specifically the case in which $a$ or $b$ are null.

a) Preliminary considerations

• $S(a,b,n)$ is clearly symmetric in $a$ and $b$;
• it is the convolution of the discrete functions of $n$ : $n^a,\; n^b$;
• it looks like the discrete analog of the integral of Bernstein basis polynomials
and actually it is proportional to the corresponding Rieman Sum
\bbox[lightyellow] { \eqalign{ & \left( \matrix{ a + b \cr a \cr} \right){{S(a,b,n)} \over {(n+1) n^{\,a + b} }} = {1 \over n}\sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{a + b \cr a \cr} \right)\left( {{k \over n}} \right)^{\,a} \left( {1 - {k \over n}} \right)^{\,a + b - a} } \buildrel {n\, \to \,\infty } \over \longrightarrow \cr & \to \;\int_0^1 {b_{\,a,\,a + b} (x)dx} = \int_0^1 {\left( \matrix{ a + b \cr a \cr} \right)x^{\,a} \left( {1 - x} \right)^{\,b} dx} = {1 \over {\left( {a + b + 1} \right)}} \cr} } \tag{1} so that we have an asymptotical relation in $n$, also having a clear
connection with the Beta function.

b) relation with S(a,0,n)

For $a,\,b$ non negative integers, developing $(n-k)^b$ we get \bbox[lightyellow] { \eqalign{ & S(a,b,n) = \sum\limits_{0\, \le \,k\, \le \,n} {k^{\,a} \left( {n - k} \right)^{\,b} } = \sum\limits_{0\, \le \,k\, \le \,n} {\left( {n - k} \right)^{\,a} k^{\,b} } \quad \left| {\;0 \le a,b \in \mathbb Z} \right. \cr & = \sum\limits_{0\, \le \,j\, \le \,b} {\left( {\left( { - 1} \right)^{\,b - j} \left( \matrix{ b \cr j \cr} \right)\sum\limits_{0\, \le \,k\, \le \,n} {k^{\,a + b - j} } } \right)n^{\,j} } = \sum\limits_{0\, \le \,j\, \le \,a} {\left( {\left( { - 1} \right)^{\,a - j} \left( \matrix{ a \cr j \cr} \right)\sum\limits_{0\, \le \,k\, \le \,n} {k^{\,a + b - j} } } \right)n^{\,j} } \cr & = \sum\limits_{0\, \le \,j\, \le \,b} {\left( {\left( { - 1} \right)^{\,b - j} \left( \matrix{ b \cr j \cr} \right)S(a + b - j,0,n)} \right)n^{\,j} } = \sum\limits_{0\, \le \,j\, \le \,a} {\left( {\left( { - 1} \right)^{\,a - j} \left( \matrix{ a \cr j \cr} \right)S(a + b - j,0,n)} \right)n^{\,j} } \cr} } \tag{2}

Concerning $S(a,0,n)$, there are four basic expressions for it \bbox[lightyellow] { \eqalign{ & S(m,0,n) = \sum\limits_{0\, \le \,k\, \le \,n} {k^{\,m} } \quad \left| {\;0 \le m,n \in \mathbb Z} \right. = \cr & = \sum\limits_{0\, \le \,k\, \le \,n} {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)} {\left\{ \matrix{ m \cr j \cr} \right\}k^{\,\underline {\,j\,} } } } = \quad \quad (3.1) \cr & = \sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,m} \right)} {\;l!\;\left\{ \matrix{ m \cr l \cr} \right\}\left( \matrix{ n + 1 \cr l + 1 \cr} \right)} = \quad \quad (3.2)\cr & = \sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,m} \right)} {\left\langle \matrix{ m \cr l \cr} \right\rangle \left( \matrix{ n + 1 + l \cr m + 1 \cr} \right)} = \quad \quad (3.3) \cr & = {{n + 1} \over {m + 1}}\sum\limits_{0\, \le \,l\,\left( { \le \,m} \right)} {\left( \matrix{ m + 1 \cr l + 1 \cr} \right)\;b_{\,m - l} \;\left( {n + 1} \right)^{\,l} } \quad \quad (3.4) \cr} } where:
- ${\left\{ \matrix{ m \cr l \cr} \right\}}$ denotes the Stirling N. of 2nd kind;
- ${\left\langle \matrix{ m \cr l \cr} \right\rangle }$ denotes the Eulerian N. (Worpitzky's identity);
- $b_n$ denotes the Bernoulli N. ( in the version $b_1 = -1/2$).

c) recurrence on $n$

We can write $$\bbox[lightyellow] { \left\{ \matrix{ S(a,b,n) = 0\quad \left| {\;n < 0} \right. \hfill \cr S(a,b,0) = 0^{\,a} 0^{\,b} = \left[ {0 = a} \right]\left[ {0 = b} \right] \hfill \cr S(a,b,1) = \left[ {0 = a} \right] + \left[ {0 = b} \right] \hfill \cr S(a,b,2) = 0^{\,a} 2^{\,b} + 1^{\,a} 1^{\,b} + 2^{\,a} 0^{\,b} = 1 + 2^{\,b} \left[ {0 = a} \right] + 2^{\,a} \left[ {0 = b} \right] \hfill \cr \hfill \cr S(a,b,n) = \sum\limits_{0\, \le \,k\, \le \,n} {k^{\,a} \left( {\left( {n - 1} \right) + 1 - k} \right)^{\,b} } = \hfill \cr = n^{\,a} 0^{\,b} + \sum\limits_{0\, \le \,j\,} {\left( \matrix{ b \cr j \cr} \right)\sum\limits_{0\, \le \,k\, \le \,n - 1} {k^{\,a} \left( {n - 1 - k} \right)^{\,j} } } = \hfill \cr = n^{\,a} \left[ {0 = b} \right] + \sum\limits_{0\, \le \,j\,} {\left( \matrix{ b \cr j \cr} \right)S(a,j,n - 1)} \hfill \cr} \right. } \tag{4}$$ where, in the last two sums, the upper bound for $j$ would extend to infinity if $b$ were not an integer.
However, taking $b$ to be a non-negative integer, it is still valid for $a$ real.

d) z-Transform

From the consideration that $S(a,b,n)$ is the convolution of the two signals $n^a$ and $n^b$, all considered as functions of $n$, the (unilateral) z-Transform follows easily. We consider here $a$ and $b$ non-negative integers. \bbox[lightyellow] { \eqalign{ & F(a,z) = \sum\limits_{0\, \le \,n} {n^{\,a} z^{\,n} } \quad \left| {\,0 \le a \in \mathbb Z} \right.\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)} {\left\{ \matrix{ a \cr j \cr} \right\}z^{\,j} \sum\limits_{0\, \le \,n} {n^{\,\underline {\,j\,} } z^{\,n - j} } } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,a} \right)} {\left\{ \matrix{ a \cr j \cr} \right\}z^{\,j} \sum\limits_{0\, \le \,n} {{{d^{\,j} } \over {dz^{\,j} }}\left( {1 - z} \right)^{\, - 1} } } = {1 \over {1 - z}}\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,a} \right)} {j!\left\{ \matrix{ a \cr j \cr} \right\}\left( {{z \over {1 - z}}} \right)^{\,j} } = \cr & = {1 \over {\left( {1 - z} \right)^{\,a + 1} }}\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,a} \right)} {j!\left\{ \matrix{ a \cr j \cr} \right\}z^{\,j} \left( {1 - z} \right)^{\,a - j} } = \cr & = {1 \over {\left( {1 - z} \right)^{\,a + 1} }}\sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,a} \right)} {\left( {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,l} \right)} {j!\left\{ \matrix{ a \cr j \cr} \right\}\left( { - 1} \right)^{\,l - j} \left( \matrix{ a - j \cr l - j \cr} \right)} } \right)z^{\,l} } = \cr & = {{p_a (z)} \over {\left( {1 - z} \right)^{\,a + 1} }} \cr} } \tag{5}

So \bbox[lightyellow] { \eqalign{ & G(a,z) = \sum\limits_{0\, \le \,n} {S(a,0,n)z^{\,n} } = {{p_a (z)} \over {\left( {1 - z} \right)^{\,a + 2} }} \cr & G(a,b,z) = {{p_a (z)p_b (z)} \over {\left( {1 - z} \right)^{\,a + b + 2} }} \cr} } \tag{6}

• 1. That looks pretty interesting, the generalisation over reals is well done, however, is there a simpler closed form for integral values of a and b? – arya_stark Mar 5 '18 at 2:08
• @schrodinger_16 the formulas (3.x) are the "closest" known, and they correspond to $b=0$ (or $a=0$). So for $a,b$ general integers ($0 \le$) there won't be closer than .. the starting formula itself. – G Cab Mar 5 '18 at 10:50

Ok I am writing this as an answer because I don't feel like displaying the formula in a comment, I denote $\left\lbrace\begin{array}{l}n\\k\end{array}\right\rbrace$ the Stierling number of the second kind, i.e. the number of partitions with $k$ sets of a set with $n$ elements. You can show (to show this I use formal power series, the proof will look like my answer there Infinite Sum with Combinatoric Expression you may also used the second formula in (1) in the answer given by Robjohn for the same question, this amount to the same thing) that (there is a condition: $n\geq \alpha$):

$$\sum_{k=0}^nk^{\alpha}=\sum_{\ell=1}^{\alpha}\ell!\left\lbrace\begin{array}{l}\alpha\\\ell\end{array}\right\rbrace\binom{n+1}{\ell+1}=\sum_{\ell=1}^{\alpha}\frac{(n+1)!}{(n-\ell)!}\frac{1}{\ell+1}\left\lbrace\begin{array}{l}\alpha\\\ell\end{array}\right\rbrace$$

Remarks :

• the condition is not really necessary for the first equality as long as you ask for the convention: $\binom{n+1}{\ell+1}=0$ if $\ell>n$.

• I don't know if it can be called a "closed formula" for this sum but this is the best I know.

• As far as I know you can interpret it with nice drawings for $\alpha=1,2,3$ which is kind of a combinatorial proof but probably not the kind you are looking for. If you want I can tell you more about it.

• Stierling numbers have a combinatorial interpretation, binomial coefficients too. Maybe you can guess something by just looking at the formula.

• I have been looking for a combinatorial proof a while ago. I have not been successful. Doesn't mean there doesn't exist one in the literature, of course!

• Note that it is $$k^{\,\alpha } = \sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,\alpha } \right)} {\left\{ \matrix{ \alpha \cr l \cr} \right\}\,k^{\,\underline {\,l\,} } } = \sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,\alpha } \right)} {l!\left\{ \matrix{ \alpha \cr l \cr} \right\}\,\left( \matrix{ k \cr l \cr} \right)} \quad \left| {\;0 \le \alpha \in Z} \right.$$ – G Cab Mar 3 '18 at 7:57
• while $$\sum\limits_{0\, \le \,k\, \le \,n} {k^{\,\alpha } } = \sum\limits_{0\, \le \,k\, \le \,n} {\sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,\alpha } \right)} {l!\left\{ \matrix{ \alpha \cr l \cr} \right\}\,\left( \matrix{ k \cr l \cr} \right)} } = \sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,\alpha } \right)} {l!\left\{ \matrix{ \alpha \cr l \cr} \right\}\,\left( \matrix{ n + 1 \cr n - l \cr} \right)} \quad \left| {\;0 \le \alpha ,n \in Z} \right.$$ – G Cab Mar 3 '18 at 7:58
• @GCab, agreed. Thanks for checking! I edit. – Clément Guérin Mar 3 '18 at 8:38
• @ClémentGuérin something just struck me. Can we look at possible recursion, for the given sum? We know how to solve the easy cases, like ($\alpha$,$\beta$)= (0,1) or (1,0). Is it possible to find a recursion of S($\alpha$,$\beta$) in terms of S($\alpha$-1,$\beta$), or S($\alpha$,$\beta$-2), etc, where S denotes the required sum with parameters ($\alpha$,$\beta$) – arya_stark Mar 4 '18 at 13:38