2
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ – Brian Tung Aug 25 '15 at 0:21
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Guacho Perez Aug 25 '15 at 0:59
  • 1
    $\begingroup$ 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)$ $\endgroup$ – Ross Millikan Aug 25 '15 at 4:29
  • $\begingroup$ 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)$? $\endgroup$ – Guacho Perez Sep 12 '15 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.