Question

# (a) Find a closed-form solution for this recurrence relation: an=2⋅an−1−n+1 with a1=2a (b) Prove that your closed-form solution is correct.

Sequences

(a) Find a closed-form solution for this recurrence relation: $$an=2\cdot an−1−n+1$$ with $$a1=2a$$
(b) Prove that your closed-form solution is correct.

2021-02-01

(a) Given $$an=(2an-1)-n+1$$
$$a1=2$$
Let us determine the first terms of the sequence until we notice a pettern:
$$a1=2=1+1$$
$$a2=2a1-2+1=2(2)-2=4-1=3=2+1$$
$$a3=2a2-3+1=2(3)-3=6-1=4=3+1$$
$$a4=2a3-4+1=2(4)-4=8-1=5=4+1$$
$$a5=2a4-5+1=2(5)-5=10-1=6=5+1$$
$$a6=2a5-6+1=2(6)-6=12-1=7=6+1\cdots$$
Thus we note that an=n+1 appears to hold in general.
(b) Given
$$an=(2an-1)-n+1$$
$$a1=2$$
To proof: $$an=n+1$$ for all positive integers.
Proof by induction
Let P(n) be the statement $$an=n+1$$
Basis step $$n=1$$
$$an=a1=2$$
$$n+1=1+1=2$$
Thus P(1) is true
Inductive step Let P(k) be true.
$$ak=k+1$$
We need to proof that $$P(k+1)$$ is true.
$$ak+1=2a((k+1)-1)-(k+1)+1 =(2ak)-k$$

$$=2(k+1)-k =2k+2-k =k+2 =(k+1)+1$$
Thus P(k+1) is true.
Conclusion By the principle of mathematical induction, P(n) is true for all positive integers n.