Tag Archives: sum of powers

01/03/2015 · 7:56 pm

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.

1 Comment

Filed under Number Theory

Tagged as , , ,

10/11/2014 · 3:01 pm

A ‘Sum of Squares’ Problem

Recently I came to know from a friend that the only non-trivial value of n satisfying the Diophantine equation

1^2+2^2+\dots+n^2=m^2

is n=24. And apparently, although the problem looks fairly simple, especially since we have the formula for the left hand side

\displaystyle 1^2+2^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}

the proof is hard. In fact, I was told that all proofs of this result use advanced machinery. Nevertheless, given the simple nature of the problem I was intrigued to give it a try.

So let us assume that

n(n+1)(2n+1)=6m^2.

Noting that 2n(n+1)-n(2n+1)=n, we have that n(n+1) and 2n+1 are coprime. Indeed, if g is a common factor, then g has to divide both n and 2n+1, forcing g=1. So we deduce that

\{n(n+1),2n+1\}=\{a^2,6b^2\} or \{2a^2,3b^2\}

for some integers a,b.

Clearly 2n+1\not\in \{2a^2,6b^2\}, so 2n+1\in\{a^2,3b^2\}. Hence the possibilities are:

(i) n(n+1)=2a^2, 2n+1=3b^2.

(ii) n(n+1)=6b^2, 2n+1=a^2.

First suppose that n(n+1)=2a^2. Then n(n+1)/2=a^2 is a square triangular number, so

n=\displaystyle\frac{H_{2k}-1}{2}

for some k, where P_0,P_1,\dots are the Pell numbers. and H_0,H_1,\dots are the half-companion Pell numbers, and they are given by (1+\sqrt 2)^k=H_k+P_k\sqrt 2 for each k. So we have to find all k such that

2n+1=\boxed{H_{2k}=3b^2}.

On the other hand, if 2n+1=a^2, then a=2c-1 for some integer c. Then n=2c(c-1). Hence n(n+1)=6b^2 implies

c(c-1)(2c^2-2c+1)=3b^2.

Now \gcd(c(c-1),2c^2-2c+1)=1, so \{c(c-1),2c^2-2c+1\}=\{u^2,3v^2\} for some integers u,v. Clearly c(c-1)\neq u^2, so

c(c-1)=3v^2 and 2c^2-2c+1=u^2.

So \{c,c-1,u\} is a near isosceles Pythagorean triple, i.e.

c=\displaystyle\frac{H_{2k-1}+1}{2}.

Hence

\boxed{H_{2k-1}^2-1=12v^2\Leftrightarrow P_{2k-1}^2-1=6v^2\Leftrightarrow P_{2k}P_{2k-2}=6v^2}.

The two boxed cases are what only remain to check, and they show why this actually is a difficult problem! (Refer to the articles about Fibonacci numbers in the ‘Notes and Articles’ tab above to see how little information we have on divisors of sequences of this kind.) Nevertheless, I’ll leave it here and maybe come back to it another time.

1 Comment

Filed under Number Theory

Tagged as , ,