Solve the following recurrence relations:
a) an=an-1+3(n-1), a0=1
b) an=an-1+n(n-1), a0=3
c) an=an-1+3n^2, a0=10
d) an=2an-1+n, a0=1
e) an=2an-1+2n2, a0=3
I keep getting stuck quickly on each of these
Hello,
Here are some suggestions:
Find f(n) such that b_n=a_n-f(n) has a nice property.
a-c) a_n-f(n)=a_{n-1}-f(n-1)
d) a_n-f(n)=2(a_{n-1}-f(n-1))
I think we can find f(n) as a polynomial of n.
For example,
a) f(n)-f(n-1)=3(n-1). Let f(n)=pn^2+qn.
By substituting, we see that p=3/2 and q=-3/2 works.
Thus, b_n=b_{n-1}=b_0=1.
a_n=f(n)+b_n=f(n)+b_0=(3/2)n^2-(3/2)n+1.
e) I am not sure what you mean by "2n2",
but the same method should work if this is "2n^2".
a-c) It is also common to consider the sequence obtained by
b_n=a_n-a_{n-1}.
a_n=a_0+(b_1+b_2+...+b_n).
For example,
c)a_n=a_0+3(1^2+2^2+...+n^2)
=10+3(1/6)n(n+1)(2n+1))=10+n(n+1)(2n+1)/2.
I hope it helps.