0
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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*}

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.