b) Find the sequences from the given recurrence relations
i) an+1 = 3an+n, a = 1, n 2 1
ii) an
2an-1 + 3 an-2, ao = 2, a= 3, n 2 2
Answers
Answer:
an = an−1 + 3, a1 = 2.
Then
an−1 = an−2 + 3
an−2 = an−3 + 3
an−3 = an−4 + 3
and so on and so forth. Therefore
an = an−1 + 3
= (an−2 + 3) + 3 = an−2 + 2 · 3
= (an−3 + 3) + 6 = an−3 + 3 · 3
= . . .
= a1 + 3(n − 1).
The last equality follows because a generic term is of the form an−i + 3i,
therefore when n − i = 1, i = n − 1. By plugging the initial condition, we
conclude
an = 2 + 3(n − 1).
Once the solution has been found, you may wonder how to check whether
this is the right answer. One way to do it is by proving it by induction!
Example 62. Let us provide a proof by induction for the above example.
Define P(n) = “an = 2 + 3(n − 1)00. Then P(1) = “a1 = 2”, which is the
initial condition, is true. Suppose P(k) = “ak = 2 + 3(k − 1)00 is true. We
want to prove P(k + 1).
ak+1 = ak + 3
= 2 + 3(k − 1) + 3
= 2 + 3k