# Proof of correctness of this algorithm

Assume $A$ is an array that contains sorted integers , ie $\forall\ i,j$ where $1 \le i \le j \le |A|$, $A_i \le A_j$. The numbers do not have to be unique, and the task is to check if there is at least one pair of indices $i$ and $j$ where $A_i + A_j = n$. Simple enough, here's an algorithm that does it:

CheckForPair(A, n, i, j):
if i >= j or outOfBound:
return false
v := A[i] + A[j]
if v = n:
return true
if v < n:
return CheckForPair(A, n, i + 1, j)
if v > n:
return CheckForPair(A, n, i, j - 1)

CheckForPair(A, n):
return ChcekForPair(A, n, 1, |A|)


Mathematically,

\begin{align} CheckForPair(A, n, i, j) &= \begin{cases} false & \text{if i \ge j or i < 1 or j > |A|,} \\ true & \text{if A_i + A_j = n,} \\ CheckForPair(A, n, i + 1, j) & \text{if A_i + A_j < n,} \\ CheckForPair(A, n, i, j - 1) & \text{if A_i + A_j > n} \\ \end{cases} \\ \\ CheckForPair(A, n) &= CheckForPair(A, n, 1, |A|) \end{align}

This is an algorithm I have seen somewhere else and I am trying to prove its correctness. For $i$ and $j$ that are on the very ends on the array (ie $i = 1$ and $j = |A|$), it's easy to see why it is correct since:

• if $A_i$ + $A_j < n$, then $i$ must increase because $j$ cannot increase.
• if $A_i$ + $A_j > n$, then $j$ must decrease because $i$ cannot decrease.

However, for $i$ and $j$ that are in between, I fail to see why the above still holds.

$$CFP(n,A) = \begin{cases} False& \text{if }A=[\;]\\ True& \text{if } first(A) + last(A) = n\\ CFP(n,tail(A))&\text{if }first(A)+last(A)<n \\ CFP(n,init(A))&\text{otherwise} \end{cases}$$ where $tail(A)$ means all of $A$ but the first entry, $init(A)$ means all of $A$ but the last entry and $first(A)$ and $last(A)$ mean the first and last elements of $A$ respectively.
1. |A| = 0: $CFP (n,A)=False$ in accordance with the fact that there is no indices $i,j$ with $A_i+A_j=n$.
2. We assume the algorithm is correct for arrays of length $n$: Let $A$ be an array with $|A|=n+1$. If no pair of indices $i\leq j$ with $A_i+A_j=n$ exists, then either $CFP(n,A) = CFP(n,tail(A))$ or $CFP(n,A)=CFP(n,init(A)$. By induction hypothesis, the algorithm returns the correct result in both cases. On the other hand, if a pair $i\leq j$ of indices with the desired property exists, we distinguish the following cases:
• $A_i=first(A)$: In this case, $first(A)+last(A)\geq n$ (because of how $A$ is ordered). Thus the algorithm either returns $True$ or $CFP(n,init(A))$. In the latter case $j$ is not the last index of $A$, thus the correctness of the result follows from the induction hypothesis.
• $A_j = last(A)$: Analog to the previous case.
• $first(A)<A_i\leq A_j<last(A)$: either $CFP(n,tail(A))$ or $CFP(n,init(A)$ is called. Since the a the statement is true for both $init(A)$ and $tail(A)$, the algorithm will correctly return $True$ by induction hypothesis.