Number of solutions of $x+2y+3z=2n+k$ where $1 \leq x,y,z,k \leq n$ is about $\frac 14 n^2$

Question

Let $n \in \Bbb N$ and $k \in [n]$, where $[n]=\{1,...,n\}$. I want to show:

The number of solutions $(x,y,z)$ of the equation $x+2y+3z = 2n+k$ where $x,y,z \in [n]$ is at least $cn^2$, for some constant $c$ that is independent of $n$ and $k$.

Sidenotes:

• The $2n$ term is not important to me and can be replaced by any term that depends only on $n$, if such a $c>0$ exists. for $2n$ it seems to exist.

• My aim is to show the same for general $r$ with the equation $x_1+2x_2+3x_3+...+rx_r=k+(r-1)n$ and $c$ a function of $r$ only.

In the case $r=2$ we see that $x+2y=n+k$ has at least $\lfloor\frac n2 \rfloor$ solutions, so we can take $c=\frac 13$. This is since if we start increasing $y$ then at $y=\lceil \frac k2 \rceil$ we will have a solution and then we will have a solution for $x$ in the next $\lfloor \frac n 2 \rfloor $ values of $y$. Geometrically this is a line that has a lattice point once in every two points.

This reasoning is less clear in the case $r=3$, looking at the possible solutions of $x,y$ as we increase $z$.

UPDATE

Experimenting using Python shows that for $r=3$ the number of solutions converges to $\frac 14 n^2$. It is enough to prove that there is such a constant $c$ for all large enough $n$, since then we can make $c$ smaller so that it will work for the small values of $n$ as well. The natural guesses that the number of solutions is at least $\lfloor \frac {n^2} 4 \rfloor$ or at least $\lfloor\frac n2\rfloor ^2$ are both sometimes false, though.

The script, in case anyone wants to experiment too:

from itertools import product

def number_of_solutions(n, k, r):
    return sum(1 for variables in product(range(1, n + 1), repeat=r-1) if
               (r - 1) * n + k - sum((k+2)*variables[k] for k in range(len(variables)))
       in range(1, n + 1))

def minimal_number_of_solutions_over_all_k(n, r):
    return min([number_of_solutions(n, k, r) for k in range(1, n + 1)])

def find_approximated_c(r):
    for n in range(2, 1000):
        approximated_c = minimal_number_of_solutions_over_all_k(n,r) / (n ** (r - 1))
        print(n, approximated_c)  # stabilizes on 0.25 when r=3

Answer 1

Since you are looking for "at least" then its obvious that $2n+k$ have less solutions when $k=1$ than when $k$ is very big or $k=n$ (because the partitions of a number grows exponentially), so we are left with $x+2y+3z = 2n+1$ in order to give the "at least" constant $c$.

Now $z$ can run from $1$ up to $\lfloor \frac{2n+1}{3} \rfloor$.

Now we are left with $x+2y = 2n+1-3z$ such that $z$ runs form $1$ up to $\lfloor \frac{2n+1}{3} \rfloor$.

Let $m=2n+1-3z$ so $x+2y=m$ , in how many ways we can write some integer $m$ as sum of $x+2y$ , its easy to see that when we give $y$ a fixed value, $x$ is forced into a fixed value also, so we have $\lfloor \frac{m}{2} \rfloor$ solutions.

So we arrive at this sum $\sum \limits_{z=1}^{\lfloor \frac{2n+1}{3} \rfloor} \lfloor \frac{m}{2} \rfloor = \sum \limits_{z=1}^{\lfloor \frac{2n+1}{3} \rfloor} \lfloor \frac{2n+1-3z}{2} \rfloor $.

But there is a catch in these solutions, in these solutions i made sure that $1 \leq y,z \leq n$ but not for $x$ so for some solutions $x$ could equal $0$ or $x >n$.

To correct this let $x =2n+1-3z-2y \leq n$ which means $3z+2y \geq n+1$ which means that $y \geq \frac{n+1-3z}{2}$ which means that $y \geq \lceil \frac{n+1-3z}{2} \rceil$ (solution which will be subtracted each time). until we reach that $\lceil \frac{n+1-3z}{2} \rceil < 1$

So Approximately we get this summation $\sum \limits_{z=1}^{\lfloor \frac{n+1}{3} \rfloor} \lfloor \frac{2n+1-3z}{2} \rfloor - \lceil \frac{n+1-3z}{2} \rceil + \sum \limits_{z=1+\lfloor \frac{n+1}{3} \rfloor}^{\lfloor \frac{2n+1}{3} \rfloor} \lfloor \frac{2n+1-3z}{2} \rfloor $ and because we are trying to find the "at least" we can use the fact that $x-1 \leq \lfloor x \rfloor \leq x$ and $x \leq \lceil x \rceil \leq x+1$ and with simple arithmetic we arrive at :

$$ \sum _{z=1}^{\frac{1}{3} (n+1-3)} \frac{1}{2} (-4+n)+\sum _{z=1+\frac{n+1}{3}}^{\frac{1}{3} (2 n+1-3)} \frac{1}{2} (2 n+1-3 z-2) = \frac{1}{12}(28-19n+3n^2) \approx \frac{n^2}{4}.$$

And thus concluding the proof by setting $c=\frac{1}{4}$(actually it have to be a little bit less than $1/4$).

(Note) your first side note is correct we can take for any value $c>0$ , $c n$ and apply the proof above to come up with approximation, also i think the second side note (the Generalization) is also true but proving it might be hard.