Question

Find the closed form solutions of the following recurrence relations with given initial conditions. Use forward substitution or backward substitution as described in Example 10 in the text. (a) an = -an-1, a0 = 5 (b) an = an-1 + 3, a0 = 1 (c) an = an-1 - n, a0 = 4 (d) an = 2nan-1, a0 = 3

Answer 1

a)
`a_n=(-1)^n \cdot 5`

b)
`a_n = 1 + 3n`

c)
`a_n=4-(n(n+1))/(2)`

d)
`a_n=3 \cdot 2^{(n(n+1))/(2)}`

Explanation:

We solve this using backward or forward substitution.

a) We have this:

`a_1= - a_0= (-1)a_0`

then:

`a_2= -a_1= (-1)(-1)a_0=(-1)^2 a_0`

for
`n=3` we have:

`a_3= -a_2= (-1)(-1)^2 a_0=(-1)^3 a_0`

from this, we can see that
`a_n = (-1)^n a_0` is a solution for this recurrence relation, where
`a_0=5`. This is:

`a_n=(-1)^n\cdot 5`

b) We have
`a_n=a_(n-1)+3` with
`a_0=1`. Then:

`a_1=a_0+3=1+3=4\\</p><p>a_2=a_1+3=4+3=7` but at the same time

`a_2 = a_1 + 3 =(a_0+3)+3 = a_0+ 2 \cdot 3 [/text]</p><p>for [tex]a_3` we have:

`a_3=a_2+3=7+10=4` or
`a_3=a_2+3=(a_0+2\cdot 3)+3=a_0+3\cdot 3`

by the next:

`a_4 = a_3 + 3 = (a_0 + 3\cdot 3)+3 = a_0 + 4\cdot 3`

We can see that the recurrence rule is:

`a_n=a_0+n\cdot 3`

this is
`a_n=1+n\cdot 3`

c)Note that:

`a_1-a_0 = (a_0 - 1)-a_0=-1\\a_2-a_1 = (a_1 - 2) -a_1 = -2\\a_3-a_2 = (a_2 - 3) - a_2 = -3\\\ldots\\a_n-a_(n-1) = (a_(n-1)-n)-a_(n-1) =-n`

taking all this we have to:

`a_n-a_0=\sum\limits_(k=1)^n (a_k - a_(k-1)) =\sum\limits_(k=1)^n -k = -\sum\limits_(k=1)^n k = - (n(n+1))/(2)`

then:

`a_n=a_0-(n(n+1))/(2)`

this is:

`a_n=4-(n(n+1))/(2)`

d)We take
`a_n=2^na_(n-1)`. Then:

`a_n=2^na_(n-1)=2^n(2^(n-1)a_(n-2)) = 2^n\cdot 2^(n-1)(2^(n-2)a_(n-3)) = \dots =2^n\cdot2^(n-1)\cdot2^(n-2)\cdots 2^1 a_0=2^(n+(n-1)+(n-2)+\dots + 1)a_0=2^{(n(n+1))/(2)}a_0`

replacing
`a_0=3`we have:

`a_n=3 \cdot 2^{(n(n+1))/(2)}`