In a question i found the recurrence relation $a_n=a_{n-2}+3^{(n-2)/2}$ then i should solve this relation with using generating factor but $3^{(n-2)/2}$ makes difficult to solve . Is there a solution for such a relations ? Or is my answer wrong ?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Expand the equation:
\begin{align*} a_n&=a_{n-2}+3^{\frac{n-2}{2}} \\ &=a_{n-4}+3^{\frac{n-4}{2}} + 3^{\frac{n-2}{2}} \\ &=\sum_{i=1}^{\frac{n}{2}}3^{\frac{n}{2}-i} \\ &=3^{\frac{n}{2}}\sum_{i=1}^{\frac{n}{2}}3^{-i}\\ &= 3^{\frac{n}{2}}\times \frac12 \times\left(1-\left(\frac{1}{3}\right)^{\frac{n}{2}}\right)\\ &=3^{\frac{n}{2}}\times \frac12 - \frac12\,. \end{align*}
$\begingroup$
$\endgroup$
If you're looking for an asymptotic bound, it is easier to observe that on the $n^{th}$ level we get $3^{(n-2)/2}$ but on the $(n-2)^{th}$ level, we get $3^{(n-4)/2} = 3^{(n-2)/2} \cdot 3^{-1}$, for any $n$. So at any level, the children contribute a factor of 3 less than the parent, causing the recurrence to be "root dominated". That is to say, the first level dominates asymptotically. So the total value of $a_n$ is on the order of $O(3^{(n-2)/2}) = O(3^{n/2})$.
