# Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C

So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve this recurrence relation by expanding it out and here is what I have so far: I'm not sure where to go from here and how to find the asmpytotic bounds.

• Welcome to Computer Science! 1. Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. 2. en.wikipedia.org/wiki/Geometric_series – D.W. Apr 23 '16 at 4:20
• Please specify the initial condition of the recurrence relation. What is the value of T(1) exactly. From what I can make out it is equal to c. Is this what it is? – Prateek Apr 23 '16 at 14:45
• There are $n/2$ terms and not $\log_2 n$ terms in the expansion. And why can't you do a sum on a geometric series? But your approach is correct. – Shreesh Apr 23 '16 at 15:29
• Hi. So there are n/2 terms? And yes sorry T(1) here is equal to c. I was thinking a sum of geometric series, but im not sure how to go about doing that with the constant a. Would the aspytotic bound here just be a constant? – Mike Apr 24 '16 at 7:01

The first four lines of your argument were correct; all you missed was the proper generalization. In general, we see that $$T(n) = c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j)$$ Now we want to drive $T(n-2j)$ down to a value we know, namely $T(1)=c$. To do this we'll need $n-2j=1$ and so we set $j=(n-1)/2$, giving us \begin{align} T(n) &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j)\\ &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{(n-1)/2-1}+\alpha^{(n-1)/2} c\\ &= c(1+\alpha+\alpha^2+\dotsb+\alpha^{(n-1)/2}) \end{align} and this is just a geometric series, so I'll leave the last steps to you.
The trick here is to solve a modified recurrence in which there is no constant. Let $S(n) = T(n) - C/(1-\alpha)$. Then $$S(n) = T(n) - C/(1-\alpha) = C + \alpha T(n-2) - C/(1-\alpha) = \\ C + \alpha (S(n-2) + C/(1-\alpha)) - C/(1-\alpha) = \alpha S(n-2).$$ (I found the constant $C/(1-\alpha)$ by solving linear equations.)
The solution to $S(n)$ with initial conditions $S(0),S(1)$ is easily found to be $$S(2n) = \alpha^n S(0), \qquad S(2n+1) = \alpha^n S(1).$$ It follows that $$T(2n) = \alpha^n (T(0) - C/(1-\alpha)) + C/(1-\alpha), \\ T(2n+1) = \alpha^n (T(1) - C/(1-\alpha)) + C/(1-\alpha).$$