# How many solutions to $x + y = z$ for $x,y \in [1,n]$ and $n > 1$ in general, closed form.

To restate the constraints, I have $x,y$ as strictly positive integers not exceeding $n$. As a result, the number of solutions will be nonzero on the range $z \in [2, 2n]$.

My first reaction was to do it using inclusion/exclusion. First define $x' = x-1$, $y'=y-1$, $z'=z-2$ to take care of the lower bounds.

We now have $x',y' \in [0, n-1]$. If we let $P_x := x'\le n-1$ and $P_y := y'\le n-1$ and $N(C) := \text{the number of solutions satisfying C}$, then we arrive at the following inclusion exclusion sum.

$$N(P_xP_y) = N - N(P_x') - N(P_y') + N(P_x'P_y')$$

For the unconstrained case:

$$N = \binom{2+z'-1}{z'} = z' + 1 = z - 1$$

For each of the constraints $x' \le n - 1$ and $y' \le n-1$ respective complements, i.e., $x' \ge n$, $y' \ge n$:

$$N(P_x') = N(P_y') = \binom{2+(z'-n)-1}{z'-n} = z'-n+1 = z-n-1$$

And finally for the constraint $x' \ge n \land y'\ge n$:

$$N(P_x'P_y') = \binom{2+(z'-2n)-1}{z'-2n} = z'-2n+1 = z - 2n -1$$

But obviously I've messed up somewhere, because you will note that my inclusion-exclusion sum is zero, regardless of the values taken by $n$ and $z$.

I know from the generating function below that the answer will take the form $2n-z+1$ for $z>n$ and $z-1$ otherwise (alternately, $n - |z-n-1|$), but I do not know how to prove this is true in general. Note that the first case is equal to my first three terms in my inclusion/exclusion, and the second case is equal to the first term alone.

$$(\sum_{i=1}^n g^i)^2$$

I would like to understand how to do this with inclusion/exclusion.

The inclusion-exclusion sum is correct. It is simply the case that one should not always include all terms.

The term $N(P_x'P_y')$ will be zero for any $z\le 2n$ because the sum of two numbers $a,b>\frac{c}{2}$ must be greater than $c$. Thus we can eliminate that term since we are supposing $z \in [2,2n]$.

The second and third terms are also both zero if $z \le n$ because there is no way to add a number $a>n$ with a number $b>0$ and get $a+b\le n$.

So the trivial closed form must be expressed by cases:

$$N(P_xP_y)=\begin{cases} z-1 & \quad z\in[2,n] \\ 2n−z+1 & \quad z\in(n,2n] \\ 0 & \quad \text{otherwise}\end{cases}$$

Showing that this is equivalent to $n−|z−n−1|$ on the range $z\in[2,2n]$ can be done by splitting the second equation into cases.

$$n-|z-n-1| = \begin{cases} n+z-n-1 = z-1 \quad & 0 \ge z-n-1 \\ n-z+n+1 = 2n-z-1 \quad & 0 \lt z-n-1 \end{cases}$$

Now we show that $z\in[2,n]\implies 0\ge z-n-1$. Note the equation is maximized for fixed $n$ when $z$ is maximized, so we will take $z=n$.

$$0 \ge n-n-1=-1$$

Similarly, $z\in(n,2n]\implies 0<z-n-1$. The right hand size is minimized when $z$ is minimized, for fixed $n$. Since we are dealing in integers, this is equivlaent to $z\in[n+1,2n]$. So we take $z=n+1$ and find the condition is satisfied. Note the inequality is no longer strict because the (equivalent) interval we took was closed.

$$0 \le (n+1) - n - 1 = 0$$