Turning Sequences of Numbers into Arithmetic Progressions

I've been thinking quite a bit about arithmetic progressions since I came across the problem "The Arithmetic Progression Detective" on Codewars. An arithmetic progression is a sequence of numbers such that, for any consecutive numbers $x_i$ and $x_{i + 1}$ in the sequence, $x_{i + 1} - x_i$ is always the same value, $d,$ known as the common difference. One example of an arithmetic progression is the sequence $5, 10, 15, 20, 25, 30,$ whose common difference $\textrm{is---you guessed it!---}5.$

Let $s_n$ be an arbitrary sequence of integers, or terms. Let $d_n$ be the common difference of the arithmetic progression from which $s_n$ deviates by no more than one value—the incorrect value—if such a progression exists. I'm going to call $s_n$ fixable if and only if such a progression exists. If $s_n$ cannot be turned into an arithmetic progression through the replacement of just one number in $s_n,$ then $s_n$ is not fixable. Bearing this in mind, what limits can we identify to the range of fixable sequences?

Let $s_1$ be the sequence $1, 2, 4, 5.$ Let $s_2$ be the sequence $2, 5, 6, 8.$ $s_1$ is not a fixable sequence. But $s_2$ clearly is, since $s_2$ deviates by just one number from the arithmetic progression $2, 4, 6, 8.$

$s_1$ and $s_2$ have a great deal in common. Each includes four numbers. Each superficially resembles an arithmetic progression. Each contains exactly one apparent deviation, in one sense or another: exactly one step whose size differs from the others' in the case of $s_1,$ and exactly one incorrect value in the case of $s_2.$ So what difference between these two sequences makes $s_2$ fixable and $s_1$ not?

One of the first things I noticed is, unlike $s_2,$ $s_1$ consists of steps all but one of which are the same size. To see this, note the following. The step from $2$ to $4$ in $s_1$ is of size $2.$ The remaining steps in $s_1$ are of size $1.$ By contrast, in $s_2,$ each step's a different size. Steps one through three, respectively, are of sizes $3, 1,$ and $2.$ So, the only step of size $d_2$ in $s_2$ is the third and final step, from $6$ to $8.$

This goes to show you should not take for granted that $s_n$ contains more steps of size $d_n$ than of any other size, even assuming that there are four or more values in $s_n,$ and that only one is incorrect.

But this difference between $s_1$ and $s_2$ does not fully explain their differing with respect to fixability. Some sequences are just like $s_1$ in that they consist of steps all but one of which are the same size, but they are still fixable. One such sequence is $1, 4, 6, 8.$ All you have to do to fix this is replace $1$ with $2.$ Really any sequence is fixable whose first or last term is the sole incorrect value. For our purposes the incorrect value in $s_n$ is defined as the one and only term whose replacement can single-handedly turn $s_n$ into an arithmetic progression.

What sets $s_1$ apart from a sequence whose first or final term is the only wrong one? Why is $s_1$ not fixable like that kind of sequence? An obvious response is that $s_1$ doesn't contain exactly one incorrect value. But I'm not satisfied with that answer. It's not wrong, but it's not illuminating either. It raises questions like: "How many incorrect values does $s_1$ contain? How exactly do we count them?" We need to explicate what makes a value incorrect and how we can tell a value meets that condition. Maybe the following is a better answer.

In $s_1$ we have a step of size $1,$ followed by one of size $2,$ followed by one of size $1.$ If we could turn that second step into a step of size $1,$ we'd be able to create an arithmetic progression. But if we try to do that by moving the second step's beginning closer to its end, we widen the first step; the first step ends where the second begins. If on the other hand we move the second step's end closer to its beginning, we widen the third step; the third step begins where the second ends.

So there are ways to decrease the size of the second step from $2$ to $1.$ But they all end up shortening or lengthening one of the other steps, such that it is no longer of size $1.$ (Well, more precisely, all our options have this result if we limit ourselves to replacing just one integer in $s_1$ with just one integer.) So we don't end up with an arithmetic progression.

That's where $1, 2, 4, 5$ differs from $1, 4, 6, 8.$ The latter sequence consists of a step of size $3,$ followed by two steps of size $2.$ Crucially, that first step has an endpoint that no other step has. That is, the first number in the sequence is where the first step begins, and no other step begins or ends with that term. So you can replace that term with any number you want, including a number $x$ such that $4 - x = 2.$ The substitution will affect no step but the first, which is the only one you want to change.

---

Here is a more formal proof that you cannot turn $1, 2, 4, 5$ into an arithmetic progression by replacing just one term with just one integer. We can split into two categories the integers in $s_1$ there are to replace: the numbers on the ends and those in between.

Suppose you replace exactly one of the two numbers on the ends $(\textrm{i.e., } 1 \textrm{ or } 5).$ Replacing $1$ changes only the size or direction of the first step, whereas replacing $5$ changes only the size or direction of the final step. So after you replace $1,$ the sizes of the second and third steps are still, respectively, $2$ and $1.$ And after you replace $5,$ the sizes of the first and second steps are still, respectively, $1$ and $2.$ But all the steps in the modified sequence must be the same size, if the sequence is to count as an arithmetic progression. So the modified sequence cannot be an arithmetic progression. In other words, you cannot turn $s_1$ into an arithmetic progression by replacing just $1,$ or just $5,$ with just one integer.

Suppose that instead you replace exactly one number strictly between those on the ends $(\textrm{i.e., } 2 \textrm{ or } 4).$ Let $x$ and $y$ be arbitrary integers such that $x \not= 2$ and $y \not= 4.$ Let $s_{1_x}$ be the sequence resulting from replacing $2$ with $x.$ Let $s_{1_y}$ be the sequence resulting from replacing $4$ with $y.$

Recall that $s_1$ is the sequence $1, 2, 4, 5.$ Consequently, $s_{1_x}$ is the sequence $1, x, 4, 5,$ and $s_{1_y}$ is the sequence $1, 2, y, 5.$ The first two steps in $s_{1_x}$ differ from the first two in $s_1;$ no other step in $s_{1_x}$ differs from its counterpart in $s_1.$ The final two steps in $s_{1_y}$ differ from the final two in $s_1;$ no other step in $s_{1_y}$ differs from its counterpart in $s_1.$

Let $b = x - 2, c = y - 4.$ Then $1 + b$ is the signed value representing the size and direction (on the number line) of the step from $1$ to $x$ in $s_{1_x} ,$ and $2 - b$ is that representing the size and direction of the step from $x$ to $4$ in $s_{1_x} .$ Furthermore, $2 + c$ is the signed value representing the size and direction (on the number line) of the step from $2$ to $y$ in $s_{1_y},$ and $1 - c$ is that representing the size and direction of the step from $y$ to $5$ in $s_{1_y} .$

$s_{1_x}$ or $s_{1_y}$ is an arithmetic progression only if all steps within it are of the same size and direction. Thus, $s_{1_x}$ is an arithmetic progression only if

$1 + b = 2 - b = 1.$

And $s_{1_y}$ is an arithmetic progression only if

$1 = 2 + c = 1 - c.$

But it is true neither that

$1 + b = 2 - b = 1$

nor that

$1 = 2 + c = 1 - c.$

I shall show that neither of these is true by giving a proof by contradiction of the falsity of each.

Here is a proof by contradiction that

$1 + b = 2 - b = 1$

is false.

Assume the following, arguendo:

$1 + b = 2 - b = 1$

Then:

$1 + b = 2 - b$

$1 + 2b = 2$ $\tiny (\textrm{added } b \textrm{ to both sides})$

$2b = 1$ $\tiny (\textrm{subtracted } 1 \textrm{ from both sides})$

$b = \frac{1}{2}$ $\tiny (\textrm{divided both sides by } 2)$

$2 - b = 2 - \frac{1}{2} = \frac{3}{2}$

$2 - b = \frac{3}{2}$ $\tiny (\textrm{transitivity of} =)$

But our initial assumption entails

$1 = 2 - b.$

So:

$1 = 2 - b = \frac{3}{2}$

$1 = \frac{3}{2}$ $\tiny (\textrm{transitivity of} =)$

But obviously:

$1 \not= \frac{3}{2}$

Therefore,

$1 = \frac{3}{2} \land 1 \not= \frac{3}{2}.$

Contradiction! We derived this from our initial assumption. A contradiction cannot be true, so neither can anything that entails a contradiction. Thus, our initial assumption must be false. Since this conclusion follows given an arbitrary integer $x,$ the proof just given demonstrates that $1 + b = 2 - b = 1$ is false regardless of what integer you substitute for $2$ in $s_{1}.$

Now let us prove by contradiction that

$1 = 2 + c = 1 - c$

is false.

Assume the following, arguendo:

$1 = 2 + c = 1 - c$

Then:

$2 + c = 1 - c$

$2 + 2c = 1$ $\tiny (\textrm{added } c \textrm{ to both sides})$

$2c = -1$ $\tiny (\textrm{subtracted } 2 \textrm{ from both sides})$

$c = -\frac{1}{2}$ $\tiny (\textrm{divided both sides by } 2)$

$2 + c = 2 - \frac{1}{2} = \frac{3}{2}$

$2 + c = \frac{3}{2}$ $\tiny (\textrm{transitivity of} =)$

But our initial assumption entails:

$1 = 2 + c$

So:

$1 = 2 + c = \frac{3}{2}$

$1 = \frac{3}{2}$ $\tiny (\textrm{transitivity of} =)$

But obviously:

$1 \not= \frac{3}{2}$

Therefore,

$1 = \frac{3}{2} \land 1 \not= \frac{3}{2}.$

Another contradiction! Since this conclusion follows given an arbitrary integer $y,$ the proof just given demonstrates that $1 = 2 + c = 1 - c$ is false regardless of what integer you substitute for $4$ in $s_{1}.$

Recall that $s_{1_x}$ is an arithmetic progression only if

$1 + b = 2 - b = 1.$

And $s_{1_y}$ is an arithmetic progression only if

$1 = 2 + c = 1 - c.$

But as the foregoing proofs by contradiction show, it is true neither that

$1 + b = 2 - b = 1$

nor that

$1 = 2 + c = 1 - c.$

Therefore, neither $s_{1_x}$ nor $s_{1_y}$ is an arithmetic progression. But $s_{1_x}$ is the result of replacing $2$ in $s_1$ with an arbitrary integer, and $s_{1_y}$ that of replacing $4$ in $s_1$ with an arbitrary integer. So, no matter what integer you substitute for $2$ or $4$ in $s_1,$ you don't thereby get an arithmetic progression.

But if you can't get an arithmetic progression by thus replacing just $2$ or $4,$ and you can't do so by thus replacing just $1$ or $5,$ then you can't do so by thus replacing just $1, 2, 4,$ or $5.$ But that means you can't do so by replacing just one integer with just one integer, since $1, 2, 4,$ and $5$ are all the integers there are to replace in $s_1.$

Therefore, you cannot turn $s_1$ into an arithmetic progression by replacing just one term with just one integer.

---

From the above proof, what lesson should we draw concerning sequences other than $s_1?$ This is my takeaway.

Let $s_3$ be some sequence of integers $x_1, x_2, \dots , x_{\ell-1}, x_\ell$ of length $\ell \geq 4.$ (To be clear, we know $s_3$ includes the four values $x_1, x_2, x_{\ell-1},$ and $x_\ell.$ We don't know if $s_3$ includes other values.) Let $1 \leq i \leq \ell.$ Let $x_i$ be the $i^{\textrm{th}}$ number in $s_3.$ Let $d_i = x_{i + 1} - x_i.$ Let step $i$ be the step in $s_3$ from $x_i$ to $x_{i + 1}.$ Note that replacing $x_i$ with a different integer changes only step $i - 1$ and step $i.$

Let $s_{3_z}$ be the sequence resulting from replacing $x_i$ with an arbitrary integer $z.$ Let $x_{i_z}$ be the $i^{\textrm{th}}$ number in $s_{3_z}.$ Let $d_{i_z} = x_{i + 1_z} - x_{i_z}.$ The subscript of $x_{i + 1_z}$ should be read as $(i + 1)_z,$ not as the expression $i + 1_z$ with which $1_z + i$ is interchangeable.

Replacing exactly one integer $x_i$ in $s_3$ can only turn $s_3$ into an arithmetic progression on the following condition:

$\text{\small F}\text{\tiny IXABLE}\text{\small : } \small \exists y \exists c (y - x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}).$

Here is an informal, rough English translation of the logical notation above. There are integers $y$ and $c$ such that

(I) $c$ is the difference between $y$ and $x_i,$ and

(II) lengthening step $i - 1$ (if there is one), and shortening step $i$ (if there is one), by $c$ units ensures all steps have the same size and direction.

Allow me, now, to prove that $s_{3_z}$ is not an arithmetic progression if $\neg\text{\small F}\text{\tiny IXABLE}.$

Assume the following, arguendo:

$s_{3_z}$ is an arithmetic progression, and $\neg\text{\small F}\text{\tiny IXABLE}.$

You know what we have to do. Derive a contradiction!

By the definitions of $x_i$ and $s_{3_z},$ $x_i$ is the $i^{\textrm{th}}$ number in $s_3,$ and $s_{3_z}$ is the sequence resulting from substituting $z$ for $x_i$ in $s_3.$ Thus, the $i^{\textrm{th}}$ number in $s_{3_z}$ is $z$ rather than $x_i.$ By definition, $x_{i_z}$ is the $i^{\textrm{th}}$ number in $s_{3_z}.$ So, given that $x_{i_z}$ and $z$ are each the $i^{\textrm{th}}$ number in $s_{3_z},$ it must be that $x_{i_z} = z.$

Since $x_{i_z}$ is the only number in $s_{3_z}$ that differs from the number at the corresponding position in $s_3,$

$\forall j \neq i (x_j = x_{j_z}).$

So, $x_{i + 1_z} = x_{i + 1}.$

So, by the definition of $d_{i_z},$

$d_{i_z} = x_{i + 1} - z.$

Solving for $x_{i + 1},$

$x_{i + 1} = d_{i_z} + z.$

Then, from the definition of $d_{i_z},$ we get

$d_{i - 1_z} = x_{i_z} - x_{i - 1_z}.$

So, seeing as $x_{i_z} = z$ and $x_{i - 1_z} = x_{i - 1},$ we may conclude that

$d_{i - 1_z} = z - x_{i - 1}.$

Then we solve for $x_{i - 1}$ as follows:

$x_{i - 1} = z - d_{i - 1_z}.$

Now let's take our solutions for $x_{i + 1}$ and $x_{i - 1},$ and combine them with the following information. The definition of $d_i$ implies that $x_{i + 1} = d_i + x_i$ and $x_{i - 1} = x_i - d_{i - 1}.$ Taking all these facts into account, we see both that

$d_i + x_i = x_{i + 1} = d_{i_z} + z$

and that

$x_i - d_{i - 1} = x_{i - 1} = z - d_{i - 1_z}.$

Of course, that means $d_i + x_i = d_{i_z} + z$ and $x_i - d_{i - 1} = z - d_{i - 1_z}.$ Solving both these equations for $z,$ we get

$z = x_i + d_i - d_{i_z}$

as well as

$z = x_i - d_{i - 1} - d_{i - 1_z}.$

From those two equations, we derive

$x_i + d_i - d_{i_z} = x_i - d_{i - 1} - d_{i - 1_z},$

which we simplify to

$d_i - d_{i_z} = d_{i - 1_z} - d_{i - 1}.$

From our assumption arguendo that $s_{3_z}$ is an arithmetic progression, it follows that $d_{i - 1_z} = d_{i_z}.$ Given the conjunction of this equation with $d_i - d_{i_z} = d_{i - 1_z} - d_{i - 1},$ it is provable that

$d_{i_z} = \frac{d_i + d_{i - 1}}{2},$

which can be rewritten as

$d_{i - 1} = 2d_{i_z} - d_i.$

The fact that $s_{3_z}$ is an arithmetic progression tells us the following as well:

$d_{1_z} = d_{2_z} = \dots = d_{i - 1_z} = d_{i_z} = d_{i + 1_z} = \dots = d_{\ell - 2_z} = d_{\ell - 1_z} .$

And considering that $s_{3_z}$ is indiscernible from $s_3$ apart from $z\textrm{'s}$ having been substituted for $x_i,$ this must be true:

$\forall j ((j \neq i - 1 \land j \neq i) \to d_j = d_{j_z}).$

This means that, for all numbers $j$ equal to neither $i - 1$ nor $i,$ we can replace $d_{j_z}$ with $d_j$ in the chain of equations presented immediately prior to the universally quantified generalization:

$d_1 = d_2 = \dots = d_{i - 2} = d_{i + 1} = \dots = d_{\ell - 2} = d_{\ell - 1} .$

Time for another proof by contradiction! We want to establish the truth of

$d_{i - 1} + (z - x_i) = d_i - (z - x_i),$

so we assume the negation of that for the sake of argument:

$d_{i - 1} + (z - x_i) \neq d_i - (z - x_i).$

From this we derive

$d_{i - 1} \neq 2d_{i_z} - d_i,$

which contradicts our previous conclusion that

$d_{i - 1} = 2d_{i_z} - d_i.$

Therefore,

$d_{i - 1} + (z - x_i) = d_i - (z - x_i),$

which completes our subproof!

It goes without saying that both the integer $z$ and the difference $z - x_i$ exist. So, we have found a $y$ and a $c$ such that

$y - x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}.$

If you're curious, $z$ is our $y,$ and $z - x_i$ is our $c.$ That is, we can go from

$\small z - x_i = z - x_i \land d_1 = \dots = d_{i - 1} + (z - x_i) = d_i - (z - x_i) = \dots = d_{\ell - 1}$

to

$\exists y \exists c (y - x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}).$

And then we've established $\text{\small F}\text{\tiny IXABLE}.$ So we have finally derived a contradiction from our initial assumptions. Recall what those assumptions were: $s_{3_z}$ is an arithmetic progression, and $\neg\text{\small F}\text{\tiny IXABLE}.$ From these we ultimately concluded $\text{\small F}\text{\tiny IXABLE},$ which contradicts the second of our two initial assumptions.

So, either $s_{3_z}$ is not an arithmetic progression, or $\text{\small F}\text{\tiny IXABLE}.$ But this disjunction is just another way of saying $s_{3_z}$ is not an arithmetic progression if $\neg\text{\small F}\text{\tiny IXABLE}.$

And that's what we set out to prove!