# How many unique numbers can be obtained by adding two numbers from two different sequences?

Let the two integer sequences $\{a_m\}$ and $\{b_m\}$, be defined as: $a_n+D_n=a_{n+1}$ and $b_n=a_n-k$, where $D_n$ may be any natural number (and $D_i$ may or may not be equal to $D_j$), $k$ is an integer constant, and $a_1$ is also an integer. Find how many different numbers can be obtained by adding any $a_j$ to any $b_i$.
My attempt
I found how many possible numbers I could get from the two sequences by arranging all elements of $\{a_m\}$ and $\{b_m\}$ in an addition table. The table has $m^2$ entries. But because addition of integers is commutative, it would also be diagonally symmetric, making the new amount of possible different numbers equal to $\frac {m^2+m}{2}$.
However, I noticed that by making the values of some $D_i$'s equal to each other or equal to $k$ some numbers in the table would be repeated. My best guess is that the number of repetitions in the values of $D_i$ is somehow related to the repetitions in the table, but I have no idea how to prove it.
Question
How can I find the number of repeated numbers in the table from the information above?

• Since $a_i+b_j = a_i+a_j-k$, aren't the obtainable sums just $k$ less than an ordinary addition table for the $\{a_i\}$? It seems to me you can assume $k = 0$ w.l.o.g. – Brian Tung Aug 25 '15 at 0:21

Without some information about the $D$'s there is no answer. If the $D$'s are larger than $mk$ and distinct enough, all the $m^2$ entries in the table will be distinct. The table need not be symmetric because the increments in the two axes differ. If the $D$'s all equal $k$ there will only be $2m-1$ distinct entries.
• But the table is indeed symmetric. From the definition of $a_{n+1}$ we can deduce that $a_n=a_1+\sum_{i=1}^n D_i$. From the definition of $b_n=a_n-k$ it follows that $a_i+b_j=a_j+b_i$ by substituting the two previous definitions into the equation, proving the table is symmetric. If it is symmetric, how can it have $m^2$ distinct entries? – Guacho Perez Aug 25 '15 at 0:59
• You are right. I had read it incorrectly. So $a_2+b_1=2a_1+D_1-k=a_1+b_2$ You can still have the $D$'s large and chosen so there are no coincidences in the sums (let all the $D_i$ be distinct powers of $2$ greater than $mk$, for example) so the number of distinct sums is maximal at $\frac 12m(m+1)$ – Ross Millikan Aug 25 '15 at 4:29
• And if we defined a secondary term, name it $d_{ij}=|a_i-a_j|$ between all numbers in the sequence and we added up all of these secondary terms, could we find an expression for the repetitions given that the summation was bounded by a function of $n$, $a_n$ and $a_1$, let it be $B(n,a_n,a_1)$ such that: $\sum _{i,j} d_{ij} \le B(n,a_n,a_1)$? – Guacho Perez Sep 12 '15 at 7:49