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 &gt;= j or outOfBound:
        return false
    v := A[i] + A[j]
    if v = n:
        return true
    if v &lt; n:
        return CheckForPair(A, n, i + 1, j)
    if v &gt; 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) &amp;=
\begin{cases}
false  &amp; \text{if $i \ge j$ or $i &lt; 1$ or $j &gt; |A|$,} \\
true &amp; \text{if $A_i + A_j = n$,} \\
CheckForPair(A, n, i + 1, j) &amp; \text{if $A_i + A_j &lt; n$,} \\
CheckForPair(A, n, i, j - 1) &amp; \text{if $A_i + A_j &gt; n$} \\
\end{cases} \\
\\
CheckForPair(A, n) &amp;= 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 &lt; n$, then $i$ must increase because $j$ cannot increase.
if $A_i$ + $A_j &gt; 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.
It is a recursive definition, thus we can use induction. Let me first rephrase the algorithm a bit:

$$
CFP(n,A) = 
\begin{cases}
False&amp; \text{if }A=[\;]\\
True&amp; \text{if } first(A) + last(A) = n\\
CFP(n,tail(A))&amp;\text{if }first(A)+last(A)&lt;n \\
CFP(n,init(A))&amp;\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.

We now prove the statement by induction on the length of the array:


|A| = 0: $CFP (n,A)=False$ in accordance with the fact that there is no indices $i,j$ with $A_i+A_j=n$.
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)&lt;A_i\leq A_j&lt;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.