# Given $n \in \mathbb{N}$, what numbers are representable as $a_1a_2 + \cdots + a_{k-1}a_k$, $k \geq 2$, $\sum a_k = n$, $a_i \in \mathbb{N}_+$?

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.

-
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

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.$$

-