# Find explicit form of following: $a_n=3a_{n-1}+3^{n-1}$

I wanted to find the explicit form of a recurrence relation , but i stuck in nonhomogenous part.

Find explicit form of following: $$a_n=3a_{n-1}+3^{n-1}$$ where $$a_0=1 , a_1 =4,a_2=15$$

My attempt:

For homogeneous part , it is obvious that $$c_13^n$$

For non-homogenouspart = $$3C3^n=9C3^{n-1}+3^n \rightarrow 9C3^n=9C3^{n}+3 \times3^n$$ , so there it not solution.

However , answer is $$n3^{n-1} + 3^n$$ . What am i missing ?

Hint. Divide both sides by $$3^n$$ we get $$\frac{a_n}{3^n}=\frac{a_{n-1}}{3^{n-1}}+\frac{1}{3}$$ Now we let $$b_n=\frac{a_n}{3^n}$$, so $$b_n=b_{n-1}+\frac{1}{3}$$.

• A general strategy of solving this type of problem if constructing similar structures (like $\frac{a_n}{3^n}$ above). Jun 1 at 14:53

The homogeneous part has solution in $$3^n$$ and the RHS part also has $$3^n$$ so you need to search for a particular solution of the form $$(an+b)3^n$$.

When you have a root $$r$$ of the characteristic equation of multiplicity $$m$$ and if the RHS is $$P(n)r^n$$ with $$P$$ polynomial then you need to search for a particular solution of the form $$Q(n)r^n$$ with $$Q$$ polynomial and $$\deg(Q)=\deg(P)+m$$

Note that in the case RHS is $$P(n)\alpha^n$$ with $$\alpha$$ not a root, then we just say $$m=0$$.

Here $$r=3,\ m=1$$ (single root of $$r-3=0$$) and $$P(n)=\frac 13$$ is a constant, thus a polynomial of degree $$0$$, so $$Q$$ is of degree $$1$$ or simply $$Q(n)=an+b$$.

Let $$A(z)=\sum_{n \ge 0} a_n z^n$$ be the ordinary generating function. The recurrence relation and initial condition imply that \begin{align} A(z) &= a_0 + \sum_{n \ge 1} a_n z^n \\ &= 1 + \sum_{n \ge 1} (3a_{n-1} + 3^{n-1}) z^n \\ &= 1 + 3z \sum_{n \ge 1} a_{n-1} z^{n-1} + z \sum_{n \ge 1} 3^{n-1} z^{n-1} \\ &= 1 + 3z \sum_{n \ge 0} a_n z^n + z \sum_{n \ge 0} (3z)^n \\ &= 1 + 3z A(z) + \frac{z}{1-3z}. \end{align} Solving for $$A(z)$$ yields \begin{align} A(z) &= \frac{1+z/(1-3z)}{1-3z} \\ &= \frac{1-2z}{(1-3z)^2} \\ &= \frac{2/3}{1-3z} + \frac{1/3}{(1-3z)^2} \\ &= \frac{2}{3}\sum_{n\ge 0}(3z)^n + \frac{1}{3}\sum_{n\ge 0}\binom{n+1}{1}(3z)^n \\ &= \sum_{n\ge 0}\left(\frac{2}{3}+\frac{1}{3}(n+1)\right)3^n z^n \\ &= \sum_{n\ge 0}(n+3)3^{n-1} z^n. \end{align} Hence $$a_n=(n+3)3^{n-1}$$ for $$n \ge 0$$.