3
$\begingroup$

There are two arithmetic series. There may be common terms between two sequences. We have to prove whether or not common terms between two series also form an arithmetic series. If yes what is first term and common difference of this series.

Update:

I formulated this problem while solving an algorithm design problem. Under this problem we have different base number systems (2, 3, .... 35). We are given m suffixes (s1, s2, s3,....,sm) expressed in base number systems (b1, b2, b3, .... , bm) respectively. We have to find minimum number which when expressed in bases (b1, b2, b3....,bm) has suffix string (s1,s2,s3,...sm) respectively. Alphabets used are (0,1,2....9, A,B,C,...,X,Y,Z).

For example, we have following three base-suffix pairs

5 22 (base 5 and suffix 22; a = 12,d = 25)

11 A2 (base 11 and suffix A2; a = 112,d = 121)

18 4 (base 18 and suffix 4; ; a = 4,d = 18)

In this case required output is 112 in decimal.

Numbers that satisfy base-suffix pair condition form an arithmetic series. So to find minimum number that satisfy all base-suffix pair conditions we have to find an arithmetic series whose terms are common to all arithmetic series. This is the origin of problem I stated before.

$\endgroup$
  • 1
    $\begingroup$ Welcome to math stack exchange. This is a learning community, so we are happy to help... but we expect you to share what you've tried and where you are stuck. Here's a good reference about asking a good (and well received) question: meta.math.stackexchange.com/questions/9959/… $\endgroup$ – TravisJ Apr 21 '15 at 2:11
  • 2
    $\begingroup$ If you were given concrete pairs of series, it would be good to mention them, and any attempt you made to solve the problem. A general abstract discussion is possible, but may be ill-suited to your needs. $\endgroup$ – André Nicolas Apr 21 '15 at 2:11
  • $\begingroup$ I think it's a great question, but it is indeed missing context. $\endgroup$ – Don Larynx Apr 21 '15 at 14:46
1
$\begingroup$

Suppose that $a_n=a_0+a'n$ and $b_n=b_0+b'n$ are the arithmetic progressions. If there is at most one common term, then obviously it is not an arithmetic progression, and if $a'$ and $b'$ have different signs (one is increasing and one is decreasing), then there are only finitely many common terms so it is not an arithmetic progression. Otherwise, suppose that $a_i=b_k$ and $a_j=b_m$ are the first two common terms, so that $0\le i<j$ and $0\le k<m$ (we can choose $i<j$, and $k<m$ is a consequence of the fact that the sequences are either both increasing or both decreasing).

Now let $c_n=a_i+n(a_j-a_i)$. This is an arithmetic progression, and I claim that all common terms are of this form. To see that every $c_n$ is a common term, note that since

$$a_r+(a_j-a_i)=(a_0+a'r)+(a_0+a'j)-(a_0+a'i)=a_0+a'(r+j-i)=a_{r+j-i},$$

if $a_r=b_s$ is a common term, then so is $a_r+(a_j-a_i)=b_s+(b_m-b_k)$. And then since $c_0$ is a common term, by induction every $c_n$ is.

Now suppose that $a_p=b_q$ is the $p$-minimal common term that is not equal to $c_n$ for any $n$. Since $a_i=b_k$ and $a_j=b_m$ are the first two common terms, which are equal to $c_0$ and $c_1$ by construction, we know $i<j<p$, so $p'=p-(j-i)$ is strictly between $i$ and $p$, and $q'=q-(m-k)$ is between $k$ and $q$. But by the same calculation as above, $a_{p'}=b_{q'}$, so it is a common term, and if it were a $c_n$ for some $n$ then $a_p$ would be $c_{n+1}$, so we conclude that $a_{p'}=b_{q'}$ is another common term not equal to any $c_n$, in contradiction to the minimality of $p$. Thus $c_n$ enumerates all common terms.

$\endgroup$
0
$\begingroup$

If a sequence of values follows a pattern of adding a fixed amount from one term to the next, it is referred to as an arithmetic sequence. The number added to each term is constant (always the same).

HINT If the sequences contained more than one common term, what does this tell you about their common differences (can the progression be non-linear)? What if there is only one common term - is this series also an arithmetic sequence, and how? Zero common terms?

These are all of the cases you must examine.

Drawing pictures will really help a lot.

$\endgroup$
  • $\begingroup$ I interpret the question differently. The sequences $1,4,7,10,\dots$ and $2,4,6,8,10,\dots$ have common terms $4,10,16,24,\dots$ which form an arithmetic progression. $\endgroup$ – Mario Carneiro Apr 21 '15 at 7:03
  • $\begingroup$ Did you mean: $4, 10, 16, 22$? @MarioCarneiro $\endgroup$ – Don Larynx Apr 21 '15 at 14:45
  • $\begingroup$ You'd think I'd learn how to add by now -_- $\endgroup$ – Mario Carneiro Apr 21 '15 at 20:09

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.