Question

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

Answer 1

$$d=a_n-a_{n-1}=-1$$

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.$