Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Could someone give me a little hint how to solve this ?

Given a number $n\in\mathbb{N},\ n\geq 3$ and the set

$S_n = \{ \left. m \in \mathbb{N}\setminus\left\{0\right\} \ \right| \quad \exists k \in \mathbb{N},\ k \geq 2,\ \exists a_1, \ldots, a_k \in \mathbb{N}\setminus\left\{0\right\}\ \text{such that}\ a_1 + \cdots + a_k = n$ $\text{and} \ a_1a_2 + a_2a_3 + \cdots + a_{k-1}a_k = m\} $

one has to find an explicit description of this set.

I thought about it a bit and it seems to me, that $S$ should be of the form $S_n=\left\{ 1,2,\ldots,n \right\} $ but I have no idea how to attempt a proof.

share|cite|improve this question
Something is wrong. There should be some $m$'s in the definition of $S_n$. – Beni Bogosel May 30 '11 at 8:45
Got it; thanks. – resu May 30 '11 at 10:54
Try some small values of $n$ and see if there's a pattern. For $n=3$, the only possibilities are $1+2=3$ and $1+1+1=3$, both give $m=2$, so $S_3=\lbrace2\rbrace$. I get $S_4=\lbrace3,4\rbrace$. $S_5=\lbrace4,5,6\rbrace$. – Gerry Myerson May 30 '11 at 12:24
resu, can you find $\min S_n$ and $\max S_n$? – Yuval Filmus May 30 '11 at 15:31
Yet another hint: what is the biggest value you can get if you fix $k=2$? What do you get if you fix $k=n$? – Alexander Thumm May 30 '11 at 18:23
up vote 1 down vote accepted

This is not a complete answer, only a prove of the bounds $\min S_n$ and $\max S_n$.

Let $\mathbb N = \lbrace 1,2,3,\dots\rbrace$ denote the positive integers.

We first prove $\min S_n = n-1$ by induction:

Let $a_1,a_2 \in \mathbb N$, then it is easily verified, that $a_1a_2 \geq a_1 + a_2 - 1$.

Now assume, that for $k \geq 2$ and for all $a_1, \dots, a_k \in \mathbb N$ we know that $$a_1a_2 + \dots a_{k-1}a_k \geq a_1 + \dots + a_k - 1$$

is true, then we conclude

$$a_1a_2 + \dots + a_{k-1}a_k + a_ka_{k+1} \geq$$ $$(a_1 + \dots + a_{k-1} + a_k - 1) + a_ka_{k+1} =$$ $$a_1 + \dots + a_{k-1} + a_k(1 + a_{k+1}) - 1 \geq$$ $$a_1 + \dots + a_k + a_{k+1} - 1.$$

This inequality assures $\min S_n \geq n-1$. If we choose $a_1 = \dots = a_n = 1$, then $a_1a_2 + \dots + a_{n-1}a_n = n-1$.

Now we will show $\max S_{2n} = n^2$ and $\max S_{2n+1} = n(n+1)$:

Let $a_1,a_2 \in \mathbb N$ with $a_1 + a_2 = 2n$ (resp. $a_1 + a_2 = 2n+1$), then it is obvious, that $a_1a_2 \leq n^2$ (resp. $a_1a_2 \leq n(n+1)$) and the bound is actually taken.

We will prove the rest of this part only for the even case (the odd case being completely analogous).

If we have $a_1, a_2, a_3 \in \mathbb N$ satisfying $a_1 + a_2 + a_3 = 2n$, then $a_1a_2 + a_2a_3 = a_2(a_1 + a_3) \leq n^2$.

Now assume we know, that for some $k\geq3$ and for all $a_1, \dots ,a_k \in \mathbb N$ with $a_1 + \dots + a_k = 2n$ we have $a_1a_2 + \dots + a_{k-1}a_{k} \leq n^2$.

Let $a_1, \dots, a_{k+1} \in \mathbb N$ with $a_1 + \dots + a_{k+1} = 2n$, then

$$a_1a_2 + \dots + a_{k-2}a_{k-1} + a_{k-1}a_k + a_ka_{k+1} =$$ $$a_1a_2 + \dots + a_{k-2}(a_{k-1} + a_{k+1}) + (a_{k-1} + a_{k+1})a_k - a_{k-2}a_{k+1} \leq$$ $$n^2 - a_{k-2}a_{k+1} < n^2.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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