# How many different combinations of non-negative integers $i, j$ can give the same value for $n\left(i+j\right)+j$?

For a natural number $$n$$ and non-negative integers $$i,j$$ I want to evaluate:

$$\sum_{k=n\left(i+j\right)+j}2^k$$

For this, I need to know how many possible combinations of $$i$$ and $$j$$ can give a certain value $$k$$, but I can't find any solution. Where $$n$$ is some natural number constant and $$i$$ and $$j$$ can get any non-negative integer value. Obviously, $$k{\geq}n$$ or $$k=0$$.

I've played a little with the numbers, and I reached the expression $$\left\lfloor\frac{k}{2^n}\right\rfloor+1$$ which seems to be an upper limit on the value, but I can't prove it analytically, see graph below. Number indicates the value of $$n$$, "upper lim" is the graph of $$\left\lfloor\frac{k}{2^n}\right\rfloor+1$$

Since $$k=n(i+j)+j\iff \frac{k-ni}{n+1}=j$$ for any given $$k$$ and $$n$$, the maximum possible value of $$j$$ occurs when $$i=0$$ and it is $$\frac{k}{n+1}$$.

Since $$j$$ must be a nonnegative integer, it follows that $$j$$ will lie in $$\{0,1,2,\dots,\left\lfloor \frac{k}{n+1}\right \rfloor\}$$.

We perform the substitution $$p=i+j$$. It will suffice to find the number of pairs of values of $$p$$ and $$j$$ s.t. $$k=np+j$$. Since $$k$$ is fixed, it is enough that we find the number of possible values of $$p$$ (for which constraints on both $$p$$ and $$j$$ are satisfied).

Since $$j\in \{0,1,2,\dots,\left\lfloor \frac{k}{n+1}\right \rfloor\}$$, $$k-j\in \{k,k-1,k-2,\dots,k-\left\lfloor\frac{k}{n+1}\right\rfloor\}$$. But $$k-j=np$$ assuming that $$j$$ and $$p$$ satisfy the equation.

This means that the number of possible values of $$p$$ (i.e. the number of pairs of values for $$i$$ and $$j$$) equals the number of multiples of $$n$$ in $$\{k,k-1,k-2,\dots,k-\left\lfloor\frac{k}{n+1}\right\rfloor\}$$.

This gives us that the number of pairs of values of $$i$$ and $$j$$ satisfying the conditions (for nonzero $$k$$) is $$\left\lfloor\frac{k}{n}\right\rfloor-\left\lfloor\frac{k-\left\lfloor\frac{k}{n+1}\right\rfloor-1}{n}\right\rfloor$$

I think this can be simplified to $$\left\lfloor\frac{k}{n}\right\rfloor-\left\lfloor\frac{k-1}{n+1}\right\rfloor$$

(I'm not entirely sure why this is well-bounded by $$\left\lfloor\frac{k}{2^n}\right\rfloor$$+1, but I did notice that the 'number-of-pairs' function grows very slowly with $$k$$ - perhaps the large denominator of $$2^n$$ is a significant limiting factor in the size of $$\left\lfloor\frac{k}{2^n}\right\rfloor$$+1, rendering its growth comparable to that of the 'number-of-pairs' function initially but for very large values the upper bound and the function grow disparate.)

Note: If there's anything wrong or confusing in my answer, feel free to edit it (and comment please) or just comment

• Where does the $-1$ in $\left\lfloor\frac{k-\left\lfloor\frac{k}{n+1}\right\rfloor-1}{n}\right\rfloor$ come from? – SIMEL Jan 30 at 22:39
• Say it was just $\left\lfloor\frac{k-\left\lfloor\frac{k}{n+1}\right\rfloor}{n}\right\rfloor$. In $\left\lfloor\frac{k}{n}\right\rfloor-\left\lfloor\frac{k-\left\lfloor\frac{k}{n+1}\right\rfloor}{n}\right\rfloor$, we'd be subtracting the no. of multiples of $n+1$ $\leq k-\left\lfloor\frac{k}{n+1}\right\rfloor$ from the no. that are $\leq k$. But this means that even if $k-\left\lfloor\frac{k}{n+1}\right\rfloor$ was a multiple of $n$ it wouldn't be counted, even though the interval $\{k,k-1,k-2,\dots,k-\left\lfloor\frac{k}{n+1}\right\rfloor\}$ contains $k-\left\lfloor\frac{k}{n+1}\right\rfloor$ – Cardioid_Ass_22 Jan 31 at 11:28