Use iteration, either forward or backward substitution, to solve the recurrence relation an=an−1−1 for any positive integer n, with initial condition, a0=1. Use mathematical induction to prove the solution you find is correct.

Arithmetic progression

$a, a+d, a+2d,...$

$a_n=a+d(n-1)$

$a_n=a-n+1$

Let $P(n)$ be the proposition that $a_n=a-n+1$ for any positive integer $n.$

Basis Step:

$P(1)$ is true, because

$a_1=a-1+1=a$

Inductive Step:

Assume that $P(k)$ holds for an arbitrary positive integer $k.$ That is, we assume that

$a_k=a-k+1$

Under this assumption, it must be shown that $P(k + 1)$ is true, namely, that

$a_{k+1}=a-(k+1)+1$

is also true.

$a_{k+1}=a_k−1$

Substitute

$a_{k+1}=a-k+1−1=a-(k+1)+1$

$a_{k+1}=a-(k+1)+1$

This last equation shows that $P(k + 1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step

We have completed the basis step and the inductive step, so by mathematical induction we know that $P(n)$ is true for all positive integers $n.$ That is, we have proven that

$a_n=a-n+1$

for all positive integers $n.$