Tag Archives: partition

A combinatorial identity

$(*)\qquad\qquad\qquad\displaystyle\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk=4^n$.

One way to prove it is to count the number of possible triples $(A,B,C)$ of sets with $C\subseteq B\subseteq A\subseteq S=\{1,\dots,n\}$. This can be done in two ways. First, if $A, B, C$ contain $i,j,k$ elements respectively then the number of such triples clearly equals the left-hand side of $(*)$. On the other hand, since each element of $S$ must belong to one of the four disjoint regions in the picture below

the number of such triples equals precisely $4^n$.

An algebraic proof can be obtained by repeated use of the binomial theorem:

$\displaystyle 4^n=\sum_{n\ge i\ge 0}\binom ni3^i=\sum_{n\ge i\ge j\ge 0}\binom ni\binom ij2^j=\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk$.

Similarly, one obtains the more general identity

$\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\binom{n}{i_1}\binom{i_1}{i_2}\cdots\binom{i_{m-1}}{i_m}=(m+1)^n$.

This also follows from the multinomial theorem since the left-hand side equals

$\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\frac{n!}{(n-i_1)!(i_1-i_2)!\cdots (i_{m-1}-i_m)!i_m!}=(m+1)^n$.

Filed under Combinatorics

Sums of equal powers

Let $k$ be a fixed positive integer. Let

$S_k(n):=1^k+\cdots+n^k$.

Let us consider expressions of the form

$\pm 1^k\pm\cdots\pm n^k=\displaystyle\sum_{j=1}^nj^ke_j=: S(e_1,\dots,e_n)$

where $e_j=\pm 1\,\forall j$.

Note that $S$ takes $2^n$ possible values in $[-S_k(n),S_k(n)]$ which are all congruent modulo $2$. Hence the number of distinct values that $S$ takes is at most

$\displaystyle\left\lceil\frac{2S_k(n)+1}{2}\right\rceil=S_k(n)+1$

Since this is $O(n^{k+1})$, it is eventually dominated by $2^n$. Thus for all sufficiently large $n$, we can find $e_j,e_j'\in\{\pm 1\}$ such that

$\displaystyle\sum_{j=1}^nj^ke_j=\sum_{j=1}^nj^ke_j'\Leftrightarrow\sum_{j=1}^n(e_j-e_j')j^k=0$

with $e_j\neq e_j'$ for some $j$.

Note that $e_j-e_j'\in\{0,\pm 2\}\,\forall j$. Let $A=\{j:e_j-e_j'=2\}$ and $B=\{j:e_j-e_j'=-2\}$. Then $A$ and $B$ are non-empty and disjoint, $A\cup B\subseteq\{1,\dots,n\}$, and

$\displaystyle\sum_{j\in A}j^k=\sum_{j\in B}j^k$.

Thus:

Proposition. Let $k$ be a fixed positive integer. Then one can find distinct positive integers $x_1,\dots, x_r,y_1,\dots,y_s$ such that

$x_1^k+\cdots+x_r^k=y_1^k+\cdots+y_s^k$.

In particular, one can choose $x_i,y_j\le\min\{n\in\mathbb N: 2^n>S_k(n)+1\}\,\forall i,j$.

Example. Let $k=4$. Note that $2^n>S_4(n)+1$ for all $n\ge 20$. So there exist distinct integers $1\le x_i,y_j\le 20$ such that $\sum_ix_i^4=\sum_jy_j^4$. In particular, one has

$1^4+2^4+9^4=3^4+7^4+8^4$

as well as

$7^4+8^4+10^4+13^4=3^4+9^4+14^4$.

Likewise, for fifth powers we can find such $x_i$‘s and $y_j$‘s in $[1,26]$.

This wikipedia article contains many results related to sums of powers.