How do you find the general term on the recurrence relation?

Question

How do you find the general term of this recurrence relation?

$b_n = 3b_{n-1}+3^{n-1}, n \geq 2$

$b_1 = 1$

Thank you.

Answer 1

Well the technique for solving these is generally to solve for a particular solution of the form $b_n=k3^n$ and then add a solution to the homogeneous part $b_n=3b_{n-1}$. The issue here is that $3^n$ solves the homogeneous part and so $k3^n$ doesn't help with the particular solution.

The way out is to write $b_n=3^na_n$ and solve for $a_n$ - you will see that there is some convenient cancellation. In fact $b_n=3^{n-1}a_n$ works slightly better - and you can see that this gives $b_1=a_1$. Either will do.

If you do more work with this kind of recurrence you will come to know that the particular solution here is of the form $b_n=p(n)3^n$ with $p$ a polynomial in $n$. Here the recurrence is first order and the auxiliary equation has just one root equal to $3$ - so you need a linear polynomial $p(n)=qn+r$. In second order cases where a double root occurs you will need to go to terms in $n^2$. You can prove this using the same trick as above, which takes out the power part of the problem and reduces to a polynomial case.

Answer 2

Let $c_n=\frac {b_n} {3^{n}}$. verify that $c_n=c_{n-1} +\frac 1 3$. Can you finish?

Answer 3

This is what I derived from Kavi's hint.

$b_n = 3b_{n-1}+3^{n-1}$

dividing both sides by $3^n$,

$\frac{b_n}{3^n} = \frac{b_{n-1}}{3^{n-1}} + \frac{1}{3}$

Let $c_n = \frac{b_n}{3^n}$. Then

$c_1 = \frac{b_1}{3} = \frac{1}{3}$,

$c_n = c_1 + (n-1)\frac{1}{3} = \frac{n}{3}$

$\frac{b_n}{3^n} = \frac{n}{3}$

$b_n = 3^{n-1}n$