Tag Archives: partition

A combinatorial identity

While tutoring today a student asked me about the following 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

screenshot-2016-10-03-21

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.

Leave a comment

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.

Leave a comment

Filed under Number theory