2
$\begingroup$

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 ?

$\endgroup$
7
$\begingroup$

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}$.

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

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$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy